Solved | A | B | C | D | E | F | G | H | I | J |
5/11 | AC | AC | AC | AC | AC |
ZOJ - 4104 - H
题意:给你一个序列,每次可以把一个元素移到最前面,问你移几次使得序列单增。
解法:偏思维, 做法比较多;
其实比较一下两个序列就好了;
#include<bits/stdc++.h> using namespace std; #define pb push_back typedef long long ll; const int N=1e5+5; ll a[N],b[N]; int main(){ int n, t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]),b[i]=a[i]; sort(b+1,b+1+n); int cnt=n; for(int i=n;i>=1;i--)if(b[cnt]==a[i])cnt--; printf("%d\n",cnt); } return 0; }View Code
G - G
题意:钓鱼,每个鱼钓的时间为ti,煮鱼的时间为k;问你怎么分配,使得时间最少;
解法:偏思维;
在ai%k的时间里,有两种选择,1.干等着,2.去捉鱼。
干等着:时间被浪费;
去钓鱼:保证桶里有鱼。
可以想一下,如果时间最少,那么锅的利用效率肯定最高,尽量不要让锅闲着。
那么每次在 ai%k 的时间里,如果手里有鱼,那么干等着就行了,反正锅里的鱼煮熟以后还能再放鱼,锅不会闲着;
如果手里没有鱼,那这段时间就要去捉鱼,因为不能锅闲着。
记录一下在煮鱼的时间里能钓的鱼为x,那么n-x条鱼就需要另外花k来钓;
那么有x条鱼,煮这这些鱼的时候干等着就行了,剩下的n-x就需要去钓其他鱼。
#include<cstdio> #include<algorithm> #include<queue> #define rep(i,j,k) for(int i=(int)j;i<=(int)k;i++) #define per(i,j,k) for(int i=(int)k;i>=(int)j;i++) #define pb push_back using namespace std; typedef long long ll; ll a[200005]; int main(){ int n,k,t; scanf("%d",&t); while(t--){ scanf("%d%d",&n,&k); ll ans=k,cnt=0; rep(i,1,n){ scanf("%d",&a[i]); ans+=a[i]/k*k; // cnt+=a[i]/k; a[i]%=k; } sort(a+1,a+1+n); ll x=ans/k; // if(x>n)x=n; x=min(x,n); ans+=(n-x)*k; for(int i=1;i<=x;i++)ans+=a[i]; printf("%lld\n",ans); } return 0; }View Code
F - F
题意:一个序列,每个数可以+1,-1,不变。但始终>0,问你最后形成的最大集合的元素个数。
做法:这题比较简单,搞错了一点,WA了几发;
贪心时先check ai-1,ai,ai+1;
要说也能明白,
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=150001; ll a[N]; set<ll>st; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); sort(a+1,a+1+n); for(int i=1;i<=n;i++){ if(a[i]-1>0&&st.find(a[i]-1)==st.end())st.insert(a[i]-1); else if(a[i]>0&&st.find(a[i])==st.end())st.insert(a[i]); else if(a[i]+1>0&&st.find(a[i]+1)==st.end())st.insert(a[i]+1); } int ans=st.size(); cout<<ans<<endl; return 0; }View Code