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

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：

CPP

#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;
}

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

文章操作

Update 2025/10/7

题意解释

思路

AC Code：

相关推荐

评论

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