一点问题
查看原帖
一点问题
1226854
ANDER_楼主2024/7/15 07:31

这是 AC 之前的一个思路,WA 了 10 个点,求调。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 5;;
int n, a[N], b[N], dp[N], ans[N];
void write() {
	cout<<"Yes"<<endl;
	for(int i = 1 ; i <= n ; i ++) {
		cout<<ans[i]<<" ";
	}	
	return;
}
signed main() {
	ios::sync_with_stdio(false);
	cout.tie(0);
	cin.tie(0);
	cin>>n;
	for(int i = 1 ; i <= n ; i ++) {
		cin>>a[i]>>b[i];
		if(dp[i - 1] + b[i] >= 0 && dp[i - 1] + a[i] <= 0) {
			dp[i] = 0;
		} else { 
			dp[i] = abs(dp[i - 1] + a[i]) < abs(dp[i - 1] + b[i]) ? dp[i - 1] + a[i] : dp[i - 1] + b[i];
		}
		ans[i] = dp[i] - dp[i - 1];
	}
//	write();
//	cout<<dp[n];
	if(dp[n] == 0) {
		write();
		return 0;		
	} else if(dp[n] > 0){
		for(int i = 1 ; i <= n ; i ++) {
			dp[n] -= (ans[i] - a[i]);
			if(dp[n] <= 0) {
				ans[i] = a[i] - dp[n];
				write();
				return 0;
			} else {
				ans[i] = a[i];
			}
		}
	} else {
		for(int i = 1 ; i <= n ; i ++) {
			dp[n] += (b[i] - ans[i]);
			if(dp[n] >= 0) {
				ans[i] = b[i] + dp[n];
				write();
				return 0;
			} else {
				ans[i] = b[i];
			}
		}
	}
	cout<<"No";
	return 0;
}

2024/7/15 07:31
加载中...