题目要求
更换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~
附上代码: