牛客小白月赛87 E

小苯的数组构造

题目链接

题目大意： 有一个数组a，存在数组b，使ai = ai+bi，使得a有序（非递减），同时max{b1,b2,b3...}-min{b1,b2,b3...}要最小，求数组b

分析: 一道贪心，首先对数组b整体加或者减一个数，对答案没有影响，那就令b[1]=0。其次对一个数做减法可以转化为对另外一个数做加法，所以可以令bi>0。从而确定贪心策略,如果一个数小于前面的最大值便加上一个数。

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

int n;
int a[200010];
int b[200010];
int s[200010];
int main(){
	ios;
	cin>>n;
	s[0]=-1e9;b[1]=0;
	for(int i = 1;i<=n;++i){
		cin>>a[i];
		s[i] = max(s[i-1],a[i]);
		if(i>1&&a[i]<s[i-1]) b[i] = s[i-1]-a[i];
	}
	for(int i =1;i<=n;++i) cout<<b[i]<<" ";
	return 0;
}