题目传送门

题目分析

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);
}