CF1516题解

Weak_Konjak · 2021-04-24 11:41:46 · 题解

题意

将数组中的数进行最多k次的变换：一个数加一，另一个数减一，使得数组最小。

这里的数组最小指优先比较前面的数最小，再比较后面的数最小。

即 [2, 1 ,0, 3] < [3 ,1 ,2 ,0]

分析

既然要使数组最小，就要使前面的数尽可能小

对前面的数进行减小操作，就要对另一个数进行增加操作。

为了使数组最小，应当给最后一个数增加。

解法

从第一个数往后开始，尽可能将其减小为0

并增加最后一个数的大小

代码

#include<iostream>
#include<cstdio>
using namespace std;
int a,n,t,k;
int main()
{
    cin>>t;
    while(t--){
        cin>>n>>k;
        int add=0;
        for(int i=1;i<n;i++){
            cin>>a;
            if(a>=k) a-=k,add+=k,k=0;
            else k-=a,add+=a,a=0;
            cout<<a<<' ';
        }
        cin>>a;
        cout<<a+add<<'\n';
    }

}