当前位置: 首页 > >

1452B Toy Blocks

发布时间:

题目链接


题意

给定n个盒子a





a


i




a_i


ai?表示第i个盒子中积木的数量。


可以将一些额外的积木放置到n个盒子中,使得下面的操作成立,将需要的额外的积木的最小值输出。


任意选中一个i,将





a


i




a_i


ai?中的所有积木放到其他n-1个盒子中,存在一种方案能够使n-1个盒子中的积木数量相等。
思路
s为现有积木的总个数mx为盒子中最大的积木个数k为将所有积木放到n-1个盒子中的*均值(向上取整)






k


=


?



s



n


?


1




?



k = lceilfrac{s}{n-1} ceil


k=?n?1s??


为了能够将积木放到n-1个盒子中,并且盒子中的积木数相等,需要使得
积木总数 =




m


a


x


(


m


x


,


k


)


×


(


n


?


1


)



max(mx, k) imes (n - 1)


max(mx,k)×(n?1)


数据范围:




2





n





1



0


5



,


0






a


i






1



0


9




2 le n le 10^5, 0 le a_i le 10^9


2≤n≤105,0≤ai?≤109


AC的代码

#pragma warning(disable : 4996)
#include
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, mx = 0;
long long s = 0;
cin >> n;
for (int i = 0; i < n; i++){
int temp;
cin >> temp;
mx = max(mx, temp);
s += temp;
}
int k = (s + n - 2) / (n - 1);
int res = max(mx, k);
cout << 1LL * res * (n - 1) - s << endl;
}
return 0;
}



友情链接: