一道性质+贪心好题...
相关题目:太极剑

时间限制:2000ms 空间限制:512MB -O2

题目描述

在学习太极之后,Bob 要求 Alice 教他太极剑。Alice 告诉他首先需要通过一项基本剑术测试。测试要求 Bob 尽可能快地切断 nn 根绳子。

所有绳子的端点两两不同,所以共有 2n2n 个端点。这些端点被捆在一个圆上,等距离分布。我们把这些端点按顺时针方向编号为 112n2n

Bob 每次切割的轨迹是一条直线,可以将所有与这条直线相交的绳子切断,他想知道至少多少次可以切断所有的绳子。

输入输出格式

输入格式: 第一行一个整数 n(1n2×105)n(1 \leq n \leq 2 \times 10^5),表示绳子的个数。

接下来 nn 行,每行两个整数 ,表示第 ii 根绳子的两个端点的编号。

输出格式: 一行一个整数,表示答案。

Sample Input

2
1 2
3 4
3
1 2
3 4
5 6
3
1 3
2 4
5 6

Sample Output

1
2
1

说明

样例一解释:19179.png

样例二解释:19180.png

样例三解释:19181.png

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;
#define _ 0
#define inf 1048576

int n, nxt[800005], v[800005], ans=inf;

int calc(int x) {
int r=0;
for(int ed=n+x;x<ed;x=nxt[x],++r);
return r+1>>1;
}

int main() {
scanf("%d",&n), n<<=1;
int x, y, sx, sy;
for(int i=1;i<=n/2;++i) {
scanf("%d%d", &x,&y);
if(x>y) swap(x,y);
if(y-x<sy-sx) sx=x, sy=y;
v[x]=y,v[y]=n+x,v[n+x]=n+y,v[n+y]=inf;
}
nxt[2*n]=inf;
for(int i=n*2-1;i;--i) nxt[i]=min(v[i], nxt[i+1]);
for(int i=sx;i<=sy;++i) ans=min(ans, calc(i));
printf("%d\n", ans);
return ~~(0^_^0);
}