同花顺

【题目描述】

所谓同花顺，就是指些扑克牌，它们花相同，并且数字连续。现在我有 n 张扑克牌，但它们可能并不能凑成同花顺。我现在想知道，最

少更换其中的多少张牌，我能让这 n 张牌都凑成同花顺？

【输入格式】

第个整数 n，表扑克牌的张数。

接下来 n ，每两个整数 ai 和 bi。其中 ai 表第 i 张牌的花，bi 表第 i 张牌的数字。

【输出格式】

个整数，表最少更换多少张牌可以达到标。

【样例输入 1】

1 1

1 2

1 3

1 4

1 5

【样例输出 1】

【样例输入 2】

1 9

1 10

2 11

2 12

2 13

【样例输出 2】

【数据范围】

对于 30% 的数据，n ≤ 10。

对于 60% 的数据，n ≤ 105，1 ≤ ai ≤ 105，1 ≤ bi ≤ n。

对于 100% 的数据，n ≤ 10^5，1 ≤ ai, bi ≤ 10^9。

【解题思路】

关于测试数据，我也是笑了，你从哪里找那个多颜色，想想一堆五颜六色的扑克牌上写着一堆零……画面太美不敢看

言归正传，离线处理，按照花色和大小双关键字排序，

 1 program card1;
 2 type cardd=record
 3 a,b:longint;
 4 end;
 5 var card,b:array[0..100001] of cardd;
 6 n,sum,i,j,ans,max:longint;
 7 
 8  procedure sort1(l,r: longint);
 9       var
10          i,j,x,p: longint;
11          y:cardd;
12       begin
13          i:=l;
14          j:=r;
15          x:=card[(l+r) div 2].b;
16          p:=card[(l+r) div 2].a;
17          repeat
18            while (card[i].a<p) or ((card[i].a=p) and(card[i].b<x)) do
19             inc(i);
20            while (p<card[j].a) or ((card[j].a=p) and(card[j].b>x))do
21             dec(j);
22            if not(i>j) then
23              begin
24                 y:=card[i];
25                 card[i]:=card[j];
26                 card[j]:=y;
27                 inc(i);
28                 j:=j-1;
29              end;
30          until i>j;
31          if l<j then
32            sort1(l,j);
33          if i<r then
34            sort1(i,r);
35       end;
36 begin
37     assign(input,'card.in'); reset(input);
38     assign(output,'card.ans'); rewrite(output);
39     read(n);
40     for i:=1 to n do
41      read(card[i].a,card[i].b);
42     sort1(1,n);
43     sum:=0;
44     for i:=1 to n do
45     begin
46         if (card[i-1].a<>card[i].a) or(card[i-1].b<>card[i].b) then
47         begin
48             inc(sum);
49             b[sum]:=card[i];
50         end;
51     end;
52     max:=0;
53     for i:=1 to sum do
54     begin
55         ans:=0;
56         for j:=i downto 1 do
57         begin
58             if (b[j].a=b[i].a) and (b[i].b-b[j].b+1<=n) then//前缀和
59             inc(ans)
60             else break;
61         end;
62         if ans>max then max:=ans;
63     end;
64     writeln(n-max);
65     close(input);
66     close(output);
67  end.

枚举从每个花色中的每张牌作为最大值，然后寻找最小值（此处需要前缀和，否则会是O（n^2）的复杂度），最后找出最值即可！