题解：CF2126D This Is the Last Time

HPXXZYY · 2025-07-20 14:31:11 · 题解

你有一个初始硬币价值 k 和 n 个操作，每个操作形如 [l_{i},r_{i},\text{real}_{i}]。对于每个操作，如果你当前的硬币价值满足 l_{i} \leq \text{cur} \leq r_{i}，则你的硬币价值变成 \text{real}_{i}。你可以按任意次序进行任意次操作，求最终最大的可能的硬币价值。

贪心。

显然，r_{i} 对于我们是没有用的，因为当 \text{cur}>\text{real}_{i} 时就算满足条件你也不会进行操作；当 \text{cur}<\text{real}_{i} 时，\text{cur} 当然也小于 r_{i}。所以，我们将操作化简为 [l_{i},R_{i}]，其中 R_{i}=\text{real}_{i}，当 l_{i}\leq \text{cur} \leq R_{i} 时，可以将 \text{cur} 变成 R_{i}。

按操作的 l 从小到大进行排序，如果 \text{cur} \geq l_{i}，就贪心的进行操作，最终答案一定最优。

为什么这样贪心是正确的呢？是否有这样的可能，我们需要先进行某次操作 v 使得 \text{cur} 变小，进入另一个操作 u 的区间，再通过操作 u 使得 \text{cur} 变大？

其实是有这样的可能的，但是这道题不会。核心的原因在于 \text{real}_{i}\leq r_{i}。

最开始 \text{cur} 不在 u 的操作区间的原因是 \text{cur}>r_{u}，即使我们最终通过一系列花里胡哨的操作使得 \text{cur}^{'} 进入了 u 的可操作区间 [l_{u},r_{u}]，\text{cur}>r_{u}\geq \text{real}_{u}，最终变劣了。

int T,n,k,l[N],r[N],order[N];

bool cmp(int u,int v){
    if (l[u]==l[v])
        return r[u]>r[v];
    return l[u]<l[v];
}

int main(){
    T=read();
    while (T--){
        n=read();k=read();
        for(int i=1;i<=n;i++){
            l[i]=read();
            read();
            r[i]=read();
            order[i]=i;
        }

        sort(order+1,order+n+1,cmp);

        for(int i=1;i<=n;i++)
            if (l[order[i]]<=k&&k<=r[order[i]])
                k=r[order[i]];

        printf("%d\n",k);
    }

    return 0;
}