这道题按题意数组可以不用long long类型,但又两个地方会超int范围。 sum+=a[i];sum在累加的时候会超范围,所以sum要定义成long long。
int mid=l+((r-l+1)>>1);不用改成long long类型。写成防爆写法就可以了。
考试的时候如果想不清楚可以用long long。
#include<iostream>
using namespace std;
const int N=1e5;
int a[N];
int k,n;
bool check(int mid)
{
int tot=0;
for(int i=0;i<n;i++)
tot+=a[i]/mid;
if(tot>=k)
return true;
else
return false;
}
int main()
{
//freopen("xxx.out","r",stdin);
//freopen("yyy.out","w",stdout);
long long sum=0;
int max=-1;
cin >> n >> k;
for(int i=0;i<n;i++)
{
cin >> a[i];
sum+=a[i];//超int
if(a[i]>max)
max=a[i];
}
if(sum<k)
{
cout << 0;
return 0;
}
int l=1,r=max;
while(l<r)
{
int mid=l+((r-l+1)>>1);//(l+r+1)/2,超int
if(check(mid))
l=mid;
else
r=mid-1;
}
cout << l;
//fclose(stdin);
//fclose(stdout);
return 0;
}