# 14055: 【原4055】棒棒

### 题目描述

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

### 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 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(){
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(){