codeforces 贪心 Road Widening

codeforces 贪心 Road Widening

题目描述：

 题目大意：一条公路分成 n 个部分，每个部分都有两个参数，路原本的宽度和草地的宽度，现在可以把草地修剪成路面，但修改后的相邻两段路面的宽度差的绝对值不超过 1, 问最多清除多少草地。

算法思想：贪心 or 遍历

        对于每一段路面，我们确定其下界与上界。x[i] 表示 i 段路面的最短宽度， y[i] 表示 i 段路面的最长宽度。

        仅需要一次遍历就可以了吗？

        我们需要从左往右和从右往左都遍历一遍！

#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>
#include <numeric>
#include <string>
#define ll long long 
#include<set>
#include<bitset>int main() {int parts; cin >> parts;vector<int> roads(parts); vector<int> lawns(parts);for (int i = 0; i < parts; i++) {cin >> roads[i] >> lawns[i];}// 每一个部分都有一个上界一个下界，画出这些上界和下界，相邻部分只能差 1 或者 0vector<int> x(parts);  // 下界vector<int> y(parts);  // 上界x[0] = roads[0]; y[0] = roads[0] + lawns[0];for (int i = 1; i < parts; i++) {x[i] = max(x[i] - 1, roads[i]);y[i] = min(roads[i] + lawns[i], y[i - 1] + 1);if (x[i] > y[i]) {cout << -1 << endl; return 0;}}for (int i = parts - 2; i >= 0; i--) {x[i] = max(x[i + 1] - 1, x[i]);y[i] = min(y[i + 1] + 1, y[i]);if (x[i] > y[i]) {cout << -1 << endl; return 0;}}ll ans = 0;for (int i = 0; i < parts; i++) {ans += y[i] - roads[i];}cout << ans << endl;for (int i = 0; i < parts; i++) {cout << y[i] << " ";}cout << endl;
}