题解：P13594 『GTOI - 1A』Bath

贪！给我狠狠的贪！

考场思路：

如果存在最小合法调温次数 ，则当前调温次数 在最优策略下一定也合法。 故考虑二分答案转化为可行性问题，即如何判断是否合法。

然后发现自己像只春猪，既然都有办法弄出最优策略了，在检测的同时记录一下次数即可，为什么非得套个二分答案？

操作如下：

1. 合并同一时间的调节温度结果 ；
2. 扫描时区间 记录操作 时，当前时刻之前可能的水温区间；
3. 对于时刻 ，不调温就必须能找到温度 使得：
4. 不调温，下一次水温区间就是交集部分；
   要调温，下一次水温区间与之前无关，重置最大范围 ；

正确性很显然：

• 不存在一个交集为空却不用调温的情况；
• 目前可行调温没有意义，因为上次调温可取任意值，导致当前值落在区间内任意位置；

复杂度

• map 合并 。（时间瓶颈在这里，看来二分答案亏得不多 QAQ）
• 顺序扫描一次：。

记得开 long long。

Folding Code

#include<bits/stdc++.h>
#define LL long long

using namespace std;

LL n, s, L, R;
LL a, x;

map<int, LL> delt;

LL ans;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> s >> L >> R;
    for (int i = 0; i < n; ++i) {
        cin >> a >> x;
        delt[a] += x;
    }

    LL curL = s, curR = s;
    for (auto& t : delt) {
        LL newL = max({curL, L, L - t.second});
        LL newR = min({curR, R, R - t.second});
        if (newL <= newR) {
            curL = newL + t.second;
            curR = newR + t.second;
        } else {
            ans++;
            curL = L;
            curR = R;
        }
    }
    cout << ans;
    return 0;
}