题意: 求H的最大值, H是指存在H篇论文,这H篇被引用的次数都大于等于H次.
思路:题意得, 最多只有N遍论文,所以H的最大值为N,
常识得知H的最小值为0.
所以H的答案在[0,N]之间,二分搜一下,如果满足就提高下限,不满足则降低上限.
嗯就这样!!!!
AC code:
#include<bits/stdc++.h> using namespace std; int n; vector<int> cc(200005); int main() { bool check(int t); while(scanf("%d",&n)!=EOF) { for(int i=0;i<=n;i++) cin>>cc[i]; int minn=0; int maxx=n; int ans=0; while(minn<=maxx) { int mid=(maxx-minn)/2+minn; if(check(mid)) { minn=mid+1; ans=mid; } else maxx=mid-1; } cout<<ans<<endl;} return 0; } bool check(int t) { long long sum=0; for(int i=t;i<=n;i++) sum+=cc[i]; if(sum>=t) return true; else return false; }
这里提供另一种简单思路:直接遍历!
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
1 #include <cstdio> 2 #include <cstring> 3 using namespace std; 4 5 const int maxn = 200000+10; 6 int buf[maxn]; 7 int n; 8 9 int main() { 10 while(scanf("%d",&n)!=EOF) { 11 memset(buf,0,sizeof(buf)); 12 for(int i=0;i<=n;++i) { 13 scanf("%d",buf+i); 14 } 15 for(int i=n;i>=0;--i) { 16 buf[i] = buf[i]+buf[i+1]; 17 if(buf[i]>=i) { 18 printf("%d\n",i); 19 break; 20 } 21 } 22 } 23 return 0; 24 }