自动搬运

查看原文

来自洛谷，原作者为

	Merak **

搬运于2025-08-24 21:40:03，当前版本为作者最后更新于2017-08-21 20:32:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Ps.来重新叙述一下思路www

首先对楼下各位dalao致以深深的敬意~虽然写的很清楚了我还是没有看懂QAQ是因为我太蠢了（也就我这么笨啦）

代码和思路是结合老师讲解（没错就是我们的考试题QAQ完美0分）还有一楼的Pascal大神经过论坛里某位神犇的翻译后的c++代码写出来的~表示十分的佩服两位dalaoQWQ

——————————————————————————

题目要求

更换n张牌中的某些牌使其能够凑成同花顺，且使换掉的牌的张数最小。

思路分析

反向思考一下，我们只要求能组成的同花顺的最长长度（组成张数）l，再用n减去l即可。

怎么求l呢？

假设有这样一组样例：

6

1 7

2 8

1 9

1 10

2 2

3 5

首先我们要思考同花顺的性质：花色相同且数字连续。那么由此我们可以想到什么呢？大多数人最先想到的大概是排序吧。没错，的确需要排序，这是做出这道题的一个十分重要的基础。但是同花顺还有一个性质是花色相同，说明这个题排序并不是简单的排序。该怎么排序才能求出“颜色相同”的最长单调递增序列呢？我们可以定义一个排序法则rule（详见代码），如果两张牌颜色相同，则将它们按从小到大的顺序排序；如果颜色不同，则将他们的颜色编号从小到大排序。

排序后我们将得到这样一组数据：

1 7

1 9

1 10

2 2

2 8

3 5 排完序之后我们是不是就可以开开心心求最长序列了呢？机智的出题人显然不会这么轻易放过我们（233），TA埋了一个坑在这里面：可能会存在花色和数值均相同的扑克牌。这样就影响了我们求最大序列长度，所以我们必须要通过条件语句来筛出这些牌。我们再用一个数组b[]来记录筛出重复牌后的数据。跳过这个坑之后我们就可以开始最后的工作啦！如何求最长的序列呢？我们可以通过枚举所有区间，来判断哪个区间长度最大且满足是同色牌&&b[i].y-b[j].y+1<=n（这个判断条件非常的关键）。这个条件是怎么推出的呢？先理解b[i].y-b[j].y+1的意义：它表示区间的长度，也就是说这个区间有几张牌。当它的长度d<=n的时候，一定能够拿出足够的牌来更换这个区间中不满足条件的牌。这样我们就可以求出最大序列长度啦~

希望我把这个题的思路叙述清楚了2333~

附上代码：

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
int n,cnt=0,ans,temp=0;
struct node
{
    int x;
    int y;
}a[100003],b[100003]; 
bool rule(const node &s1,const node &s2)
{
    if(s1.x==s2.x) return s1.y<s2.y;
//这里把同色的排在一起，方便后续操作 
    else return s1.x<s2.x;
} 
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].x>>a[i].y;
    }
    sort(a+1,a+n+1,rule);
    for(int i=1;i<=n;i++)
    {
        if(a[i-1].x!=a[i].x||a[i-1].y!=a[i].y)
        {
            b[++cnt]=a[i];
        } 
        //这里我们通过if语句来筛去同色牌中数值相同的牌 
    }
    for(int i=1;i<=cnt;i++)//枚举区间右端点 
    {
        temp=0;
        //注意此处一定要写在第一个循环和第二个循环之间 
        for(int j=i;j>=1;j--)//枚举区间左端点 
        {
            if(b[i].x==b[j].x&&b[i].y-b[j].y+1<=n)
            //如果是同色牌并且张数差小于等于n则一定能够通过换牌实现同花顺 
            {
                temp++; 
            }
            else break;//不符合条件则退出 
        }
        if(temp>ans) ans=temp;//取所有可行方案中最大值 
    }
    cout<<n-ans<<endl; 
    return 0;
}