杭电多校第八场 1006 Fluctuation Limit 题解

题目大意

给定你n个范围，$[l_i,r_i]$，每个范围之间可以波动k，即$[a_i-k,a_i+k]$，问是否存在某个序列，使得每个数都在范围之内。

解题思路

比赛的时候试了一下，wa了两发就溜了。。

本来想是先从i推到i+1，然后用这个约束的范围，再倒推到i的范围，然后wa了。。

后面看题解发现有点类似，但是还是不同。

从第i个范围推到第i+1个范围，只是得到第i个能够到达的范围，但是第i+1个范围还会需要受到后面第i+2的影响。

从第i+2范围推到第i+1个范围，得到的是为了满足第i+2的范围，有哪些是第i+1范围能实现的。

所以需要正着推一遍，把条件往后面推，再用后面的条件来限制前面，就能得到最后的可行域。

完整代码

#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <cmath>
#include <stack>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

vector<pair<int, int>> v;
const int N = 1e5 + 5;
int n, k, l[N], r[N];
int a[N], b[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		cin >> n >> k;
		v.clear();
		for (int i = 1; i <= n; i++) {
			int a, b; cin >> a >> b;
			v.push_back({ a,b });
		}
		l[0] = v[0].first, r[0] = v[0].second;
		int flag = 1;
		for (int i = 1; i < n; i++) {
			l[i] = max(v[i].first, l[i - 1] - k);
			r[i] = min(v[i].second, r[i - 1] + k);
			if (r[i] < l[i]) {
				flag = 0;
				break;
			}
		}
		for (int i = n - 2; i >= 0; i--) {
			l[i] = max(l[i], l[i + 1] - k);
			r[i] = min(r[i], r[i + 1] + k);
			if (r[i] < l[i]) {
				flag = 0;
				break;
			}
		}
		if (!flag)	cout << "NO" << endl;
		else {
			cout << "YES" << endl;
			for (int i = 0; i <= n - 1; i++) {
				cout << l[i] << ' ';
			}
			cout << endl;
		}
	}
}