题解 P2652 【同花顺】

· · 题解

（开氧气优化200ms）

解题思路：将牌按花色从小到大排序，花色一样，按数字从小到大排序

对排序后的每一段花色相同的牌进行处理

处理方式：枚举由1到n的每一张牌，计算出花色相同的牌中最长上升序列最大值

计算时若不满足花色相同或两牌之间的间隙（如，2与5，间隙为2（3与4为间隙））小于等于序列中存在的最大间隙的话就更新答案

之所以要求间隙，是因为，间隙可以靠其他花色的数字来填补该间隙（特别的，对于相同颜色又相同数字的牌，间隙为0，即不需要别的牌不补来，自己进行修改）

最后输出答案用n减去满足条件的最大上升序列即可

这应该是正解，不过我写挂了，虽然有100分可能是数据太水吧

例如如下情况

6
1 1
3 2
3 7
3 8
3 9
4 7

很明显答案是3但是我写的AC代码输出的是4

聪明绝顶机智灵敏的我发现只要对同色数字维护代价最少的最大上升序列就好了，简单描述就是不管条件直接求出同种数字的最大上升序列然后不断减去相隔最大的点，直到达到条件为止

代码还是很好改的下面就不做修改了，毕竟也过了马？！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node {
    long long num,col;
} a[100001];
long long n,kinds[100001];

int cmp(node x,node y) {
    if(x.col==y.col)return x.num<y.num;
    return x.col<y.col;
}
int charge() {
    int ans=0;//maxn
    int sum=0;
    int now=1;
    for(int i=1; i<=n; i++) {
        if((a[i].col==a[i-1].col)&&(a[i].num-a[i-1].num+sum-1<=n-now-1)) {
            sum+=a[i].num-a[i-1].num-1;
            if(a[i].num!=a[i-1].num)now++;
        } else {
            ans=max(ans,now);
            sum=0;
            now=1;
        }

    }
    ans=max(ans,now);
    return n-ans;
}
int main() {
    //memset(u,1,sizeof(u));
    scanf("%lld",&n);
    for(int i=1; i<=n; i++) {
        scanf("%lld",&a[i].col);
        scanf("%lld",&a[i].num);
    }
    sort(a+1,a+n+1,cmp);
    printf("%lld",charge());
}