CF1392F

虽然标签给的很难得样子，但大概就是一个构造题吧。

如果输入已经符合，直接输出

如果不符合，最后应该会变成一个楼梯被补上某一部分的样子

那就先构造一个楼梯：第一层高度为(sum*2/n+1-n)/2

然后再从头到尾扫一遍，补上去就行

下附代码：

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ll long long
 4 using namespace std;
 5 int n;
 6 ll a[1000005];
 7 int main(){
 8     scanf("%d",&n);
 9     ll sum=0;
10     for (int i=1; i<=n; i++){
11         scanf("%lld",&a[i]);
12         sum+=a[i];
13     }
14     int flag=1;
15     for (int i=1; i<n; i++){
16         if (a[i+1]-a[i]>1) {
17             flag=0;
18             break;
19         }
20     }
21     if (flag){
22         for (int i=1; i<=n; i++)
23             printf("%lld ",a[i]);
24         return 0;
25     }
26     ll x=(sum*2/n+1-n)/2,tot=0;
27     for (int i=1; i<=n; i++){
28         a[i]=x-1+i;
29         tot=tot+a[i];
30     }
31     for (int i=1; i<=n; i++){
32         if (tot<sum){
33             if (a[i]<a[i+1] || i==n) {
34                 a[i]++;
35                 tot++;
36             }
37         }
38         else {
39             break;
40         }
41     }
42     for (int i=1; i<=n; i++)
43         printf("%lld ",a[i]);
44     printf("
");
45     return 0;
46 }

View Code