题解 | 牛客周赛 Round 33

F题 方法：贪心+区间合并 具体解题思路：

代码（Java）

import java.util.*;
public class Main{
    static long ans=0;
    static Stack<long[]> stack=new Stack<>();
    public static void main(String args[]){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            long a=sc.nextInt();
            if(stack.isEmpty()||a>stack.peek()[1]+1){
                stack.push(new long[]{a,a});
            }
            else{
                //a<=stack.peek()[1]，此时需要修改前一个区间的辐射范围
                while(!stack.isEmpty()&&a<=stack.peek()[1]){
                    long b[]=stack.pop();
                    if(!stack.isEmpty()){
                        //需要跟前一个区间再次进行比较
                        long c=stack.peek()[1];
                        //最多集体下降数值为d
                        long d=b[0]-c-1;
                        if(b[1]-d>=a+(b[1]-b[0]+1)*d-1){
                            //此时这个区间可以集体下降，并且跟上一个区间合并：
                            a+=(b[1]-b[0]+1)*d;
                            ans+=d*(b[1]-b[0]+2)*(b[1]-b[0]+1)/2;
                            long e[]=stack.pop();
                            stack.push(new long[]{e[0],b[1]-d});
                        }
                        else{
                            a=find(b,a);
                        }
                    }
                    else{
                        a=find(b,a);
                    }
                }
                long b[]=stack.pop();
                b[1]++;
                stack.push(b);
            }
        }
        System.out.println(ans);
        for(long a[]:new ArrayList<>(stack)){
            for(long i=a[0];i<=a[1];i++){
                System.out.print(i+" ");
            }
        }
    }
    static long find(long b[],long a){
        //返回a的最终数值
        long c=b[1]-b[0]+1;//区间长度
        long d=(b[1]-a+1)/(c+1);//下降的高度
        ans+=d*c*(c+1)/2;
        a+=d*c;
        //此时必然还是a<=b[1]，需要增长的高度为
        b[0]-=d;
        b[1]-=d;
        d=b[1]+1-a;
        //数组的前d个数字
        long e[]=new long[]{b[0]-1,b[0]+d-2};
        ans+=(c*2-d+1)*d/2;
        if(stack.isEmpty()||stack.peek()[1]<e[0]-1){
            stack.push(e);
        }
        else{
            stack.push(new long[]{stack.pop()[0],e[1]});
        }
        stack.push(new long[]{b[0]+d,b[1]});
        return b[1]+1;
    }
}