可爱萌新学不懂 OI,求助
查看原帖
可爱萌新学不懂 OI,求助
852144
Loser_Syx楼主2024/1/7 17:05

思路是贪心放,碰到剩下的都不行的再往前面放。

#include <ctime>
#include <iostream>
#include <cassert>
#include <queue>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <bitset>
using namespace std;
#define int long long
#define debug puts("qwq")
#define open(x) freopen(#x".in", "r", stdin);freopen(#x".out", "w", stdout);
#define close fclose(stdin);fclose(stdout);
#define all(x) x.begin(), x.end()
namespace FastIO {
	template <typename T = int>
	inline T read() {
		T s = 0, w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		return s * w;
	}
	template <typename T>
	inline void read(T &s) {
		s = 0;
		int w = 1;
		char c = getchar();
		while (!isdigit(c)) {
			if (c == '-') w = -1;
			c = getchar();
		}
		while (isdigit(c)) s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
		s = s * w;
	}
	template <typename T, typename... Args> inline void read(T &x, Args &...args) {
		read(x), read(args...);
	}
	template <typename T>
	inline void write(T x, char ch) {
		if (x < 0) x = -x, putchar('-');
		static char stk[25];
		int top = 0;
		do {
			stk[top++] = x % 10 + '0', x /= 10;
		} while (x);
		while (top) putchar(stk[--top]);
		putchar(ch);
		return;
	}
} using namespace FastIO;
const int N = 1e6+19;
int b[N], p[N], u[N], ans[N][3];
struct DSU {
	int f[N];
	void init(int n) {
		for (int i=1;i<=n;++i) f[i]=i;
	}
	int find(int x) {
		if (x == f[x]) return x;
		return f[x]=find(f[x]);
	}
	void merge(int x) {
		f[x] = find(x-1);
	}
} dsu;
signed main() {
	int n = read();
	dsu.init(n);
	for (int i=1;i<=n;++i) read(b[i]);
	for (int i=1;i<n;++i) read(p[i]);
	for (int i=1;i<n;++i) read(u[i]);
	int more=b[1];
	for (int i=1;i<n;++i) {
		more=b[i+1]+more+u[i]-p[i]>b[i+1]?b[i+1]:b[i+1]+more+u[i]-p[i];
		if (more<0) return puts("NO"),0;
	}
	puts("YES");
	int cnt=0;
	more=b[1];
	for (int i=1;i<=n;++i) {
		ans[i][0]=p[i]<=more?p[i]:more;
		more=p[i]<=more?b[i+1]:more-p[i];
		if (more<0) {
			more=-more;
			ans[i][2]=more<=b[i+1]?more:b[i+1];
			more=b[i+1]-more;
			if (more<0) {
				more=-more;
				ans[i][1]=more>=u[i]?u[i]:more;
				more=more>=u[i]?more-u[i]:0;
				u[i]-=ans[i][1];
				cnt+=ans[i][1];
				if (more) {
					dsu.merge(i);
					for (int j=dsu.find(i-1);more;j=dsu.find(j-1)) {
						if (more<=u[j]) {
							ans[i][1]+=more;
							ans[i][2]-=more;
							u[j]-=more;
							cnt+=more;
							more=0;
						} else {
							ans[i][1]+=u[j];
							ans[i][2]-=u[j];
							more-=u[j];
							cnt+=u[j];
							u[j]=0;
						}
						if (u[j]==0) dsu.merge(j);
					}
				}
			}
		}
	}
	write(cnt, '\n');
	for (int i=1;i<n;++i) write(p[i]-ans[i][1]-ans[i][2], ' '), write(ans[i][1], ' '), write(ans[i][2], '\n');
	return 0;
} 
2024/1/7 17:05
加载中...