CF1516A

A. Tit for Tat

这个题不是很难。

考虑贪心。我们一定要先把前面的数字给尽量变成 \(0\),把数字全加到最后一个数身上。这一定是最优的做法。

读者自证不难

如果指针到了最后有一个数,但是 \(k\) 还不为 \(0\),就退出循环。因为题目里说:

at most \(k\) operations

读者可以自己想一下,如果没有 at most 这个条件,怎么做,也挺简单的。

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=101;

int n,k;
int a[MAXN];

signed main() {
	int t=read();
	while(t--) {
		n=read();k=read();
		for(int i=1;i<=n;i++) {
			a[i]=read();
		}
		int p=1;
		while(k&&p<n) {
			if(a[p]<=k) {
				k-=a[p];
				a[n]+=a[p];
				a[p]=0;
				p++;
			}
			else {
				a[n]+=k;
				a[p]-=k;
				k=0;
			}
		}
		for(int i=1;i<=n;i++) {
			printf("%lld ",a[i]);
		}
		puts("");
	}
	return 0;
}
上一篇:分治算法四:二叉堆的创建


下一篇:求最深字符串Output the most inner string