A21181.同花顺

普及+/提高

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

所谓同花顺,就是指一些扑克牌,它们花色相同,并且数字连续。
现在我手里有 nn 张扑克牌,但它们可能并不能凑成同花顺。我现在想知道,最少更换其中的多少张牌,我能让这 nn 张牌都凑成同花顺?

输入格式

第一行一个整数 nn ,表示扑克牌的张数。

接下来 nn 行,每行两个整数 aia_{i}bib_{i}。其中 aia_{i} 表示第 ii 张牌的花色,bib_{i} 表示第 ii 张牌的数字。

输出格式

一行一个整数,表示最少更换多少张牌可以达到目标。

输入输出样例

  • 输入#1

    5
    1 1
    1 2
    1 3
    1 4
    1 5

    输出#1

    0
  • 输入#2

    5
    1 9
    1 10
    2 11
    2 12
    2 13

    输出#2

    2

说明/提示

  • 对于 30%30\% 的数据,n10n \le 10
  • 对于 60%60\% 的数据,n105n \le 10^{5}1ai1051 \le a_{i} \le 10^{5}1bin1 \le b_{i} \le n
  • 对于 100%100\% 的数据,n105n \le 10^{5}1ai,bi1091 \le a_{i}, b_{i} \le 10^{9}
首页