题解：P14093 [ICPC 2023 Seoul R] Product Delivery

a_gold_TomAndJerry · 2025-10-03 19:14:13 · 题解

Update 2025/10/7

感谢@songhaoxuan12345678指出的不足。添加了题意解释与具体思路。

题意解释

原题翻译

有 n 个城市，第 i 个城市有需求 S_i \in [l_i,m_i]。现有一种操作，每次操作能使得前 k 个城市供应需求，但第 i 个城市的供应量 c_i \le c_{i+1}。求最少操作能满足需求。

思路

不难看出是贪心。为找出贪心策略，使用归纳法。

• 若序列 S_i 为递增序列：易知次数为 1。
• 若序列 S_i 为两个递增序列相连形成的序列（即在递增序列中出现了 c_j>c_{j+1}）：因为序列中出现两个极值，所以在满足第一个极值的需求时第二个极值无法被满足，故次数为 2。
• 若序列 S_i 为三个递增序列相连形成的序列（即在递增序列中出现了两个 c_j>c_{j+1}）：同理，在满足前两个极值时第三个不能满足，故次数为 3。
• 若序列 S_i 为 h \in [0,n] 个递增序列相连形成的序列（即在递增序列中出现了 h-1 个 c_j>c_{j+1}）：在满足前 h-1 个极值时第 h 个不能满足，故次数为 h。

故本题就是要求数列中最长不下降子序列的总个数。因为有范围的限制，我们可以这么考虑：

• 若子序列的最大左边界大于目前元素的右边界，则重新划分子序列。
• 否则子序列更新最大左边界。

注意，因为子序列的个数至少为 1，所以最后的答案要加 1。

AC Code：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,l[maxn],r[maxn],ans=0;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d%d",&l[i],&r[i]);
    int maxp=0;
    for(int i=1;i<=n;++i){
        if(maxp>r[i]){
            maxp=l[i];
            ans++;
        }else maxp=max(maxp,l[i]);
    }
    cout<<ans+1;
    return 0;
}