hdu - 6276,2018CCPC湖南全国邀请赛A题,水题,二分

题意: 求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();
int main()
{
bool check(int t);
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<=n;i++)
cin>>cc[i];
int minn=;
int maxx=n;
int ans=;
while(minn<=maxx)
{
int mid=(maxx-minn)/+minn;
if(check(mid))
{
minn=mid+;
ans=mid;
}
else
maxx=mid-;
}
cout<<ans<<endl;}
return ; }
bool check(int t)
{
long long sum=;
for(int i=t;i<=n;i++)
sum+=cc[i];
if(sum>=t)
return true;
else
return false;
}

这里提供另一种简单思路:直接遍历!

 #include <cstdio>
#include <cstring>
using namespace std; const int maxn = +;
int buf[maxn];
int n; int main() {
while(scanf("%d",&n)!=EOF) {
memset(buf,,sizeof(buf));
for(int i=;i<=n;++i) {
scanf("%d",buf+i);
}
for(int i=n;i>=;--i) {
buf[i] = buf[i]+buf[i+];
if(buf[i]>=i) {
printf("%d\n",i);
break;
}
}
}
return ;
}

Accept Code

上一篇:160CrackMe练手 002


下一篇:ZOJ 2819 Average Score 牡丹江现场赛A题 水题/签到题