codeforces 672 D

时间:2023-03-08 16:10:36
codeforces 672 D

题目链接:http://codeforces.com/problemset/problem/672/D

题目大意:进行k次操作,每次将最大值集合中最大值-1,最小值+1,问你K次操作之后,最大值和最小值的差值是多少

思路分析:二分寻找最大值和最小值,check函数很好写,但是关键的一点需要注意,就是二分的上下限,当k非常大

时,最后的结果就已经稳定在平均数位置,如果二分上下限没有选对,就会出现最小值>最大值的情况orz

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=+;
typedef long long ll;
int a[maxn];
int n,k;
int checkmi(int x)
{
ll sum=;
for(int i=;i<n;i++)
{
if(a[i]>x) break;
sum+=x-a[i];
}
if(sum<=k) return ;
else return ;
}
bool checkma(int x)
{
ll sum=;
for(int i=n-;i>=;i--)
{
if(a[i]<x) break;
sum+=a[i]-x;
}
if(sum<=k) return ;
else return ;
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF)
{
ll sum=;
for(int i=;i<n;i++)
{scanf("%d",&a[i]);
sum+=a[i];}
sort(a,a+n);
int al,ar;
if(sum%n==) {al=sum/n,ar=sum/n;}
else {al=sum/n,ar=sum/n+;}
int l=a[],r=al;
int ansl=a[],ansr=a[];
while(l<=r)
{
int mid=(l+r)>>;
if(checkmi(mid))
{
ansl=mid;
l=mid+;
}
else r=mid-;
}
l=ar,r=a[n-];
while(l<=r)
{
int mid=(l+r)>>;
if(checkma(mid))
{
ansr=mid;
r=mid-;
}
else l=mid+;
}
printf("%d\n",ansr-ansl);
}
return ;
}