洛谷 P2652 同花顺

P2652 同花顺

求出已有的序列中最长的同花顺然后用n减去这个长度

以牌的花色为第一关键字排序，不然会wa

排序之后要判重，因为有花色和大小都一样的牌

然后枚举每张牌，以这张牌为它以前的区间的右端点，再枚举左端点，就可以了

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define maxn 1000000
 4 int n,maxx,maxl,nowl=1,cnt;
 5 struct Data{
 6     int num,x;
 7 }c[maxn],a[maxn];
 8 bool cmp(Data a,Data b) 
 9 { 
10     if(a.x==b.x) 
11     return a.num<b.num;
12     else return a.x<b.x;
13 }
14 int main()
15 {
16     scanf("%d",&n);
17     for(int i=1;i<=n;i++)
18         scanf("%d%d",&c[i].x,&c[i].num);
19     sort(c+1,c+n+1,cmp);
20     for(int i=1;i<=n;i++)
21         if(c[i-1].x!=c[i].x||c[i-1].num!=c[i].num)
22             a[++cnt]=c[i];
23     for(int i=1;i<=cnt;i++)
24     {
25         nowl=0;
26         for(int j=i;j>=1;j--)
27         {
28             if(a[i].x==a[j].x&&a[i].num-a[j].num+1<=n)    nowl++;
29             else break;
30         }
31         maxl=max(nowl,maxl);
32     }
33     printf("%d
",n-maxl);
34     return 0;
35 }

View Code