Doremy's IQ - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
很好的思维贪心题,O(N)的思维方法不好想,这里讲一个二分法。
这道题的贪心在于,显然在前面减去自己的IQ值不是很好,所以我们要尽可能的到后面减去自己的贪心值
但是我们又不知道从哪里开始减去自己的IQ值。
假设我们从 pos 开始,每遇到比自己大的就减去自己的IQ值,如果到最后IQ值是≥0的,那么这个贪心是成功的,因为这做到了尽可能到后面减去自己的贪心值
对于 1~pos-1,就随遇而安,比IQ大的输出0,比IQ小于等于的输出1
显然 pos 具有单调性,所以用二分来判断。时间复杂度:O(NlogN)
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back //vector函数 #define popb pop_back //vector函数 #define fi first #define se second const int N=1e5+10; //const int M=; //const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中 //const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中 int T,n,q,a[N]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } bool check(int x) { int t=q; for(int i=x;i<=n;i++) { if(a[i]>t) t--; if(t<0) return 0; } return 1; } int main() { // freopen("","r",stdin); // freopen("","w",stdout); T=read(); while(T--) { n=read(),q=read(); for(int i=1;i<=n;i++) a[i]=read(); int l=1,r=n; while(l+1<r) { int mid=(l+r)/2; if(check(mid)) r=mid; else l=mid; } int pos; if(check(l)) pos=l; else pos=r; for(int i=1;i<pos;i++) printf("%d",a[i]<=q?1:0); for(int i=pos;i<=n;i++) printf("%d",1); puts(""); } return 0; }
标签:ch,const,int,IQ,CF1707A,define,贪心 From: https://www.cnblogs.com/Willette/p/17084303.html