C. Load Balancing 一个序列同时加一个数和减一个数,直到最大和最小之间相差最大为1(结论可记住)

发布时间:2023年12月31日

题目:? ?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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。