codeforces592_1244E Minimizing Difference_算法日常[35/100]

题目链接

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
// By LittleBeetle, contest: Codeforces Round #592 (Div. 2), problem: (E) Minimizing Difference, Accepted, #, hack it!
#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;
}

每天一句叨叨

名誉有如江河,它所漂起的常是轻浮之物,而不是确有真份量的实体

点击查看

本文标题:codeforces592_1244E Minimizing Difference_算法日常[35/100]

文章作者:单林敏

发布时间:2019年10月15日 - 22:18:54

最后更新:2019年10月17日 - 19:20:27

原始链接:https://www.wolfdan.cn/codeforces592-1244E-Minimizing-Difference-算法日常-35-100/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

-------------------本文结束 感谢您的阅读-------------------
0%