洛谷 P2652 同花顺

题目背景

所谓同花顺,就是指一些扑克牌,它们花色相同,并且数字连续。

题目描述

现在我手里有n张扑克牌,但它们可能并不能凑成同花顺。我现在想知道,最少更换其中的多少张牌,我能让这 n 张牌都凑成同花顺?

输入输出格式

输入格式:

第一行一个整数n,表示扑克牌的张数。接下来n行,每行两个整数 ai 和 bi。其中ai表示第 i 张牌的花色,bi表示第 i 张牌的数字。

输出格式:

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

输入输出样例

输入样例#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%的数据,n<=10。

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

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

题目分析

GTY大神的神题,这是第二次做,第一次<=写成了<,结果gg,第二次在QB学堂忘记排序,结果又gg,其实说实话这道题还是挺水的,题目中的问题等价于用所给的牌组成同花顺最多有多少张牌不用换,首先我们可以想到,如果确定了一张牌作为某同花顺的结尾,那么整个同花顺是确定的,其次,如果有n张牌,那么最终组成的同花顺一定有n张,另外,对于两张完全相同的牌,一定会更换至少一张,有了以上结论,思路就显而易见了,首先将所有的牌按照花色分开,去重,排序,然后对于相同的花色,用一个队列去维护以每一张牌作结尾时能在序列中的所有牌(即维护首尾指针),然后统计出这些牌的数量,取较大值,答案就是牌的总数与这个值得差值。

代码

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# include <algorithm>
# include <iostream>
# include <cstring>
# include <cstdio>
# include <cmath>
# include <vector>
# define R register

using namespace std;

int n,c[100010],cnt,ans;
struct zx{int x,y;}a[100010];
vector <int> ca[100010];

template <typename T> void in(R T &a){
R char c = getchar();R T x=0,f=1;
while(!isdigit(c)){if(c == '-') f=-1; c = getchar();}
while(isdigit(c)) x = (x<<1)+(x<<3)+c-'0',c = getchar();
a = x*f;
}

inline bool cmp(zx a,zx b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
inline void maxx(R int &a,const int b){a>b? 0:a=b;}

int main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
in(n);
for(R int i=1; i<=n; ++i) in(a[i].x),in(a[i].y);
sort(a+1,a+n+1,cmp);
for(R int i=1; i<=n; ++i) c[i] = a[i].x;
for(R int i=1; i<=n; ++i)
{
if(c[i] != c[i-1]) cnt++,ca[cnt].push_back(0);
if(a[i].x==a[i-1].x&&a[i].y!=a[i-1].y) ca[cnt].push_back(a[i].y);
}
for(R int i=1; i<=cnt; ++i){
R int now = 0;
for(R int j=1; j<ca[i].size(); ++j)
{
while(ca[i][now]<ca[i][j]-n+1) now++;//维护队列
maxx(ans,j-now+1);
}
}
printf("%d",n-ans);
}

×

纯属好玩

扫码支持
扫码打赏,你说多少就多少

打开支付宝扫一扫,即可进行扫码打赏哦

文章目录
  1. 1. 题目背景
  2. 2. 题目描述
    1. 2.0.1. 输入输出格式
      1. 2.0.1.0.1. 输入格式:
      2. 2.0.1.0.2. 输出格式:
  3. 2.0.2. 输入输出样例
    1. 2.0.2.0.1. 输入样例#1:
    2. 2.0.2.0.2. 输出样例#1:
    3. 2.0.2.0.3. 输入样例#2:
    4. 2.0.2.0.4. 输出样例#2:
  • 3. 说明
    1. 3.0.1. 数据范围
  • 3.1. 题目分析
  • 3.2. 代码
  • ,