题解：P13594 『GTOI - 1A』Bath

· · 题解

Solution

题意为小H的洗澡水初始温度为 s 度，他能接受的温度范围是 [L, R]。在洗澡期间，有 n 个人会在不同的时刻 a_i 使用水龙头，导致水温变化 x_i（ x_i 为正表示升温，为负表示降温）。同一时刻的所有变化是同时发生的。小H可以在任意时刻调整水温到任意值，但希望调整次数最少，使得在所有时刻水温都在 [L, R] 范围内。求最少需要调整多少次。

这道题我们可以首先将所有事件按时间顺序处理，从初始温度开始，按时间顺序应用每个时刻的温度变化。

然后当某个时刻的温度变化会导致水温超出 [L, R] 范围时，必须在此前进行调整。

调整的目标是找到一个新温度 T，使得 {T + \sum\limits_{i=0}^{n-1}(x_i ,\text{at current time}) ∈ [L, R]}。

调整后，后续的温度变化基于新的 T。

为了最小化调整次数，每次调整时应尽可能选择一个温度，使得后续尽可能多的变化不会导致超出范围。这可以通过维护一个“可行温度区间”来实现。

AC code

#include <bits/stdc++.h>
using namespace std;
struct p{
    int t,x;
}a[100003];
bool cmp(p b, p c) 
{
    return b.t<c.t;
}
int n,s,l,r,ans,i,b,c;
int main() 
{
    cin>>n>>s>>l>>r;
    for(int i=0;i<n;i++)
        cin>>a[i].t>>a[i].x;
    sort(a,a+n,cmp);
    b=s,c=s;
    while(i<n)
    {
        int x=a[i].t,y=0;
        while(i<n&&a[i].t==x) 
            y+=a[i].x,i++;
        if(b+y>r||c+y<l) ans++,b=l,c=r;
        else b=max(b+y,l),c=min(c+y,r);
    }
    cout<<ans;
    return 0;
}