这道题数组用int就行,有两处会爆int:sum+=a[i]和mid=l+((r-l+1)>>1)。
sum+=a[i]解决方法是:把sum定义成long long类型。
计算mid时的解决方法是:mid=l+((r-l+1)>>1)
如果考试或比赛时想不清哪些地方会超int范围,那就都定义成long long。
#include<iostream>
using namespace std;
const int N=1e5+10;
int a[N];
int n,m;
bool check(int mid)
{
int ljh=0;
for(int i=0;i<n;i++)
ljh+=a[i]/mid;
if(ljh>=m)
return true;
else
return false;
}
int main()
{
// freopen("xxx.in","r",stdin);
// freopen("yyy.out","w",stdout);
long long sum=0;
int maxx=-1;
cin >> n >> m;
for(int i=0;i<n;i++)
{
cin >> a[i];
sum+=a[i];
if(a[i]>maxx)
maxx=a[i];
}
if(sum<m)
{
cout << "0";
return 0;
}
int l=1,r=maxx;
while(l<r)
{
int mid=l+((r-l+1)>>1);
if(check(mid))
l=mid;
else
r=mid-1;
}
cout << l;
// fclose(stdin);
// fclose(stdout);
return 0;
}