P4704 太极剑

    • 45通过
    • 1K提交
  • 题目提供者 Drench 站长团
  • 评测方式 云端评测
  • 标签 位运算,按位 构造 贪心 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

    输入输出格式

    输入格式:

    第一行一个整数 $n(1 \leq n \leq 2 \times 10^5)$,表示绳子的个数。

    接下来 $n$ 行,每行两个整数 $a_i, b_i(1 \leq a_i, b_i \leq 2n, a_i \not= b_i)$,表示第 $i$ 根绳子的两个端点的编号。

    输出格式:

    一行一个整数,表示答案。

    输入输出样例

    输入样例#1: 复制
    2
    1 2
    3 4
    输出样例#1: 复制
    1
    输入样例#2: 复制
    3
    1 2
    3 4
    5 6
    输出样例#2: 复制
    2
    输入样例#3: 复制
    3
    1 3
    2 4
    5 6
    输出样例#3: 复制
    1

    说明

    样例一解释:

    样例二解释:

    样例三解释:

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。