C. Load Balancing 一个序列同时加一个数和减一个数,直到最大和最小之间相差最大为1(结论可记住)
2023-12-31 06:11:02
题目:? ?https://atcoder.jp/contests/abc313/tasks/abc313_c
思想:1.给定一个固定的B,求使A等于B所需的最小运算次数
? ? ? ? ? ?2.在所有最大值和最小值最多相差1的B中,找出一个所需的运算次数最少的,即1
做法:构造一个b数组,每一个数先加上sum/n,然后后剩余的数分配到一部分,可以保证这样是最小的。?
代码:
// Problem: C. Load Balancing
// Contest: Codeforces - Educational Codeforces Round 3
// URL: https://codeforces.com/contest/609/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+5;
int n;
int a[N];
int main(){
cin>>n;
ll sum=0;
for(int i=1;i<=n;i++){
cin>>a[i];
sum+=a[i];
}
int b[N];
for(int i=1;i<=n;i++){
if(i<=n-sum%n) b[i]=sum/n;
else b[i]=sum/n+1;
}
sort(a+1,a+n+1);
int ans=0;
for(int i=1;i<=n;i++){
ans+=abs(a[i]-b[i]);
}
cout<<ans/2<<"\n";
return 0;
}
?
文章来源:https://blog.csdn.net/m0_73896521/article/details/135309516
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!