Codeforces Global Round 10 F. Omkar and Landslide（贪心）

本文主要是介绍Codeforces Global Round 10 F. Omkar and Landslide（贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Omkar is standing at the foot of Celeste mountain. The summit is 𝑛 meters away from him, and he can see all of the mountains up to the summit, so for all 1≤𝑗≤𝑛 he knows that the height of the mountain at the point 𝑗 meters away from himself is ℎ𝑗 meters. It turns out that for all 𝑗 satisfying 1≤𝑗≤𝑛−1, ℎ𝑗<ℎ𝑗+1 (meaning that heights are strictly increasing).

Suddenly, a landslide occurs! While the landslide is occurring, the following occurs: every minute, if ℎ𝑗+2≤ℎ𝑗+1, then one square meter of dirt will slide from position 𝑗+1 to position 𝑗, so that ℎ𝑗+1 is decreased by 1 and ℎ𝑗 is increased by 1. These changes occur simultaneously, so for example, if ℎ𝑗+2≤ℎ𝑗+1 and ℎ𝑗+1+2≤ℎ𝑗+2 for some 𝑗, then ℎ𝑗 will be increased by 1, ℎ𝑗+2 will be decreased by 1, and ℎ𝑗+1 will be both increased and decreased by 1, meaning that in effect ℎ𝑗+1 is unchanged during that minute.

The landslide ends when there is no 𝑗 such that ℎ𝑗+2≤ℎ𝑗+1. Help Omkar figure out what the values of ℎ1,…,ℎ𝑛 will be after the landslide ends. It can be proven that under the given constraints, the landslide will always end in finitely many minutes.

Note that because of the large amount of input, it is recommended that your code uses fast IO.

Input
The first line contains a single integer 𝑛 (1≤𝑛≤106).

The second line contains 𝑛 integers ℎ1,ℎ2,…,ℎ𝑛 satisfying 0≤ℎ1<ℎ2<⋯<ℎ𝑛≤1012 — the heights.

Output
Output 𝑛 integers, where the 𝑗-th integer is the value of ℎ𝑗 after the landslide has stopped.

Example
inputCopy
4
2 6 7 8
outputCopy
5 5 6 7
Note
Initially, the mountain has heights 2,6,7,8.

In the first minute, we have 2+2≤6, so 2 increases to 3 and 6 decreases to 5, leaving 3,5,7,8.

In the second minute, we have 3+2≤5 and 5+2≤7, so 3 increases to 4, 5 is unchanged, and 7 decreases to 6, leaving 4,5,6,8.

In the third minute, we have 6+2≤8, so 6 increases to 7 and 8 decreases to 7, leaving 4,5,7,7.

In the fourth minute, we have 5+2≤7, so 5 increases to 6 and 7 decreases to 6, leaving 4,6,6,7.

In the fifth minute, we have 4+2≤6, so 4 increases to 5 and 6 decreases to 5, leaving 5,5,6,7.

In the sixth minute, nothing else can change so the landslide stops and our answer is 5,5,6,7.

思路：
有点"逗你玩"的感觉。
所以按照题目的意思，因为初始是递增的，所以如果 $b [i] - b [i - 1] \geq 2$ ，那么 $b [i] - b [i - 1] - 1$ 的部分会一直向前分配直到分配不了。

所以令 $b [i] = b [i - 1] + 1$ ，将 $b [i] - b [i - 1] - 1$ 的部分拿出来平均分配，剩下的部分依次放到前面就好了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <cmath>
using namespace std;typedef long long ll;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;ll a[maxn],b[maxn];int main() {int n;scanf("%d",&n);ll sum = 0;for(int i = 1;i <= n;i++) {scanf("%lld",&a[i]);}for(int i = 1;i <= n;i++) {sum += a[i] - a[1] - (i - 1);b[i] = a[1] + (i - 1);}for(int i = 1;i <= n;i++) {b[i] += sum / n;}for(int i = 1;i <= sum % n;i++) {b[i]++;}for(int i = 1;i <= n;i++) {printf("%lld ",b[i]);}return 0;
}