luogu 同花顺

这是一道有趣的题目。

详细看代码。

 1 //xzq出品,必须精品
 2 #include<bits/stdc++.h>
 3 #define inf 0x7f
 4 using namespace std;
 5 int n,i,l,j,qiang,ans;
 6 struct node {
 7     long long xia;//xia指花色
 8     long long zi;//zi指点数
 9 } dp1[100001],dp2[100001]; //dp1[]记录原数据,dp2[]记录经过重筛的数据
10 bool cmp(node x,node y) { //排序将颜色相同的排一起,将颜色不同的按颜色的序号排序
11     if(x.xia==y.xia){
12         return x.zi<y.zi;
13     }
14     return x.xia<y.xia;
15 }
16 int main() {
17 //  freopen("card.in","r",stdin);
18 //  freopen("card.out","w",stdout);
19     cin>>n;
20     for(int i=1; i<=n; i++) {
21         cin>>dp1[i].xia>>dp1[i].zi;
22     }
23     sort(dp1+1,dp1+n+1,cmp);//因为数据不一定和题目中一样是有序的,且有利于下面的筛重复数据
24     int cnt=0;//cnt指dp2[]中数的个数
25     for(int i=1; i<=n; i++) { //判断有没有数据重复的情况
26         if(dp1[i-1].xia!=dp1[i].xia  ||  dp1[i-1].zi!=dp1[i].zi) { //如果花色和点数都不同
27             dp2[++cnt]=dp1[i];
28         }
29     }
30     /*  for(int i=1;i<=n;i++)
31         {
32             cout<<dp2[i]<<' '<<dp1[i]<<endl;
33         }
34     */  
35     for(int i=1; i<=cnt; i++) { //开始干活
36         qiang=0;
37         for(int j=i; j>=1; j--) {
38             if(dp2[i].xia==dp2[j].xia&&dp2[i].zi-dp2[j].zi+1<=n) { //判断花色是否相同且判断区间是否是连续的
39                 qiang++;
40             } else {
41                 break;
42             }
43             if(qiang>ans)ans=qiang;//记录答案
44         }
45 
46     }
47     cout<<n-ans<<endl;
48     /*  for(int i=1;i<=n;i++)
49         {
50             cout<<dp2[i]<<' 'dp1[i]<<endl;
51         }
52     */
53     return 0;
54 }

 

上一篇:2019牛客暑期多校训练营(第五场)基础DP+组合数 矩阵快速幂


下一篇:《如何有效提问》读书笔记zz