题目链接
codeforces592_1244E Minimizing Difference
题解
- 先sort
- 判断最大差距和是否在k次内,是则答案为0(if you can perform the aforementioned operation no more than k times.)(
沙雕我看题不仔细以为必须处理k次)
- 通过不断地在左右两边已经遍历到的部分的一整块依次进行加减操作(左边增加,右边减少),然后达到最大最小值靠近的目的
我一开始写的还分权值操作,但是发现只要: 让左右总是保持着相同的宽度权重,然后左右之间能均摊到的剩下的k的高度是一样的!!!所以不管k还够不够分,把k加到哪一边都是一样的
AC代码
我的代码太丑了,于是就放大佬的代码吧
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1000020;
int n,i,j,a[N],mid,opt;
long long k,s;
void init(){
scanf("%d%lld",&n,&k);
for(i=1;i<=n;i++)
scanf("%d",a+i);
sort(a+1,a+n+1);
}
void work(){
mid=n+1>>1;
for(i=1;i<=mid;i++)
s+=a[mid]-a[i];
for(;i<=n;i++)
s+=a[i]-a[mid];
if(s<=k){
printf("0");
return;
}
i=1;j=n;
opt=0;
while(i+1<j){
if(1ll*(a[i+1]-a[i])*i<=k){
k-=1ll*(a[i+1]-a[i])*i;
i++;
}
else{
a[i]+=k/i;
opt=1;
break;
}
if(1ll*(a[j]-a[j-1])*(n-j+1)<=k){
k-=1ll*(a[j]-a[j-1])*(n-j+1);
j--;
}
else{
a[j]-=k/(n-j+1);
opt=1;
break;
}
}
if(i+1==j&&opt==0)
printf("%d",a[j]-a[i]-k/i);
else
printf("%d",a[j]-a[i]);
}
int main(){
init();
work();
return 0;
}
|
每天一句叨叨
名誉有如江河，它所漂起的常是轻浮之物，而不是确有真份量的实体