Skip to content

14055: 【原4055】棒棒

题目

题目描述

author: BowenTan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4055

Description

现在,你的眼前有n(n <= 50)根棒棒。

你现在想让每根棒棒的长度都小于n,所以你不停地挑出最长的那根,并且拍它,你拍一次这根棒棒就会缩短n个单位,但是其它的棒棒会偷偷伸长1个单位。

很显然,只要你坚持不停地拍棒棒,总会使每根棒棒长度都小于n。

那你猜猜,你最少拍多少次能够达到这个目的呢?

input format

本题包含多组输入数据,数据开始首先输入数据组数T(T <= 3)。

每组数据的第一行包含一个数n(n <= 50),意义如题目描述。

第二行包含n个数,依此表示每一根棒棒的长度。

output format

对于每一组输入,都输出最少的操作次数。

sample input

3
4
3 3 3 3
3
1 0 3
10
1000 193 256 777 0 1 1192 1234567891011 48 425

sample output

0
1
1234567894848

limits

  • 对于30%的数据,每根棒棒长度不超过100000
  • 对于50%的数据,每根棒棒长度不超过10^9
  • 对于100%的数据,每根棒棒长度不超过10^17

zqy2018's solution

/*
    Hint: use greedy algorithm
*/
#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
#define REPR(temp, init_val, end_val) for (int temp = init_val; temp >= end_val; --temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n;
ll a[55];
priority_queue<ll> pq;
void init(){
    n = read();
    while (!pq.empty()) pq.pop();
    REP(i, 1, n)
        scanf("%lld", &a[i]), pq.push(a[i]);
}
void solve(){
    ll ans = 0;
    for (; ; ){
        ll tp = pq.top();
        pq.pop();
        if (tp + ans < 1ll * n) break;
        ll t = (tp + ans) / n;
        ans += t;
        tp -= t * (n + 1);
        pq.push(tp);
    }
    printf("%lld\n", ans);
}
int main(){
    int T = read();
    while (T--){
        init();
        solve();
    }
    return 0;
}