Luogu题解：P13594 『GTOI - 1A』Bath

问题分析

初始水温为\(s\)，需要保持在\([L,R]\)范围内。有\(n\)个人在不同时刻使用水龙头，会使水温发生变化。同一时刻的水温变化是同时发生的可以在任意时刻调节水温到任意值，目标是最小化调节次数。

思路

1. 将所有水温变化按时间排序，并将同一时刻的变化合并成一次变化。
2. 确定水温的可能范围，并不是具体值。
3. 当水温范围超出可接受范围时，就需要调节水温，将范围重置为可接受范围\([L,R]\)。
4. 每次调节后，继续确定新的水温范围，直到所有变化都处理完。

代码

#include<bits/stdc++.h>
#define ri register int
#define int long long
#define run_fast ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
int n, s, L, R;
map<int, int> mp;
signed main() {run_fast;cin >> n >> s;cin >> L >> R;for (ri i = 0; i < n; ++i) {int a, x;cin >> a >> x;mp[a] += x;}int ans = 0,cl = s,ch = s;for (const auto& e : mp) {int d = e.second;cl += d;ch += d;if (ch < L || cl > R) {ans++;cl = L;ch = R;} else {if (cl < L) cl = L;if (ch > R) ch = R;}}cout << ans << endl;return 0;
}