题解 P14593 猫猫虫打 CF

来口。

—mzr

题目大意

给定初始值

x=0

，和

n

个数对

{a_i,b_i}

，每选中一个数对

x

就变为

\max{(x,b_i)}

，你选中这个数对当且仅当此时

x \le a_i

，你找到一种顺序使选择的数对最多。

解题思路

初步分析

考虑分类讨论，当相邻两项

{a_i,b_i}

和

{a_{i+1},b_{i+1}}

。

$a_i<b_{i+1}$ ， $b_i>a_{i+1}$ 时，参加第 $i$ 场就无法参加第 ${i+1}$ 场，参加第 ${i+1}$ 场就无法参加第 ${i}$ 场。
$a_i<b_{i+1}$ ， $b_i<a_{i+1}$ 时，参加第 ${i+1}$ 场就无法参加第 $i$ 场，参加第 $i$ 场反而可以参加第 ${i+1}$ 场。
$a_i>b_{i+1}$ ， $b_i<a_{i+1}$ 时，交换这两项，同情况 $1$ 。
$a_i>b_{i+1}$ ， $b_i>a_{i+1}$ 时，交换这两项，同情况 $2$ 。

不难观察到按照

\max{(a_i,b_i)}

升序排序最优，其次按照

a_i

升序排序，最后考虑

b_i

，然后模拟遍历有序数组计算答案即可。

~~说的简单比赛时没想出来吃口饭想出来了，给我卡麻了。~~

代码十分简单。

code

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
inline int read() {
	int x = 0, f = 0;
	char c = getchar();
	while (!isdigit(c)) {
		f |= c == '-';
		c = getchar();
	}
	while (isdigit(c)) {
		x = x * 10 + (c ^ 48);
		c = getchar();
	}
	return f ? -x : x;
}
struct node {
	int a,b;
} a[N];
int n;
bool cmp(node x,node y) {
	if (max(x.a,x.b)==max(y.a,y.b)) return x.a==y.a?x.b<y.b:x.a<y.a;
	return max(x.a,x.b)<max(y.a,y.b);
}
signed main() {
	n=read();
	for (int i=1; i<=n; i++) {
		a[i]= {read(),read()};
	}
	sort(a+1,a+n+1,cmp);
	int ans=0,nw=0;
	for (int i=1; i<=n; i++) {
		if (nw<=a[i].a) {
			ans++;
			nw=max(nw,a[i].b);
		}
	}
	cout<<ans;
}

已严肃完成今日
很遗憾，您的《题解：P14593 [LNCPC 2025] 猫猫虫打 CF》不符合推荐标准。原因是：【中文】与【英文、数字或公式】之间应以半角空格隔开。
很遗憾，您的《题解：P14593 [LNCPC 2025] 猫猫虫打 CF》不符合推荐标准。原因是：数学公式（运算式、运算符、数学推导、参与运算的常数、作为变量的字母等）应使用 LaTeX。
很遗憾，您的《题解：P14593 [LNCPC 2025] 猫猫虫打 CF》不符合推荐标准。原因是：【中文标点符号】与【英文、数字、公式或汉字】或【汉字】与【汉字】之间不应添加多余空格；数学公式外应使用中文全角标点

题解：P14593 [LNCPC 2025] 猫猫虫打 CF

文章操作