【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【2017ACM-ICPC广西邀请赛】Duizi and Shunzi

【贪心】

问题链接:https://vjudge.net/problem/HDU-6188

一些数据:

9

1 2 3 3 4 5 5 6 7

12

2 3 4 4 5 6 6 7 8 8 9 10

5

2 2 2 2 2

6

4 4 5 5 6 6

以上数据输出:

3

4

2

3

 

Solution:

解决这道题的核心在于贪心策略。对于任意连续的三个数,假设这三个数出现次数依此是a, b, c,如果组成顺子,显然个数为t = min(a, b, c),而组成对子,则有

ceil(a / 2) + ceil(b / 2) + ceil(c / 2).    【其中ceil()表示向下取整】

显然有如下关系:

ceil(a / 2) + ceil(b / 2) + ceil(c / 2) >= \(\frac{3t}{2}\).

这表明,对于三个连续数,优先取对子会得到较大的值,即对于任意数,优先组成对子。只有在一个数是奇数时才考虑顺子。

先考虑遇到一个数出现了奇数次数,现在需要考虑是否取顺子,这时要看它之后的两个数。如果它之后的两个数都不为0,若第二个数是偶数,则应该都拿对子,因为如果第三个数大于1时,拿顺子要比拿对子的数量至少多1【因为第二个数和第三个数各自组成对子】,这时就可以忽略第一个数即不用拿顺子了;当第二个数是偶数时,如果第三个数是1,这时拿对子至少能拿一个【即第二个数有两个】,而拿顺子则固定只能拿一个了【因为第一个数自己拿完对子后最多只能剩下1,且这里讨论的情况保证第三个数也只有1个】,所以我们那对子总不会差于拿顺子。当第二个数有奇数个时,先拿完对子,剩下了1个,此时第一个数也剩下了1个,只要第三个数不是0个,无论奇偶,拿第三个数全拿对子或在这里取一个顺子剩下的全拿对子没有区别,因为最多只会拆开一个对子,而拆开一个对子后我们又拿了一个顺子,最后数量不会变化。

由此得出贪心策略:

对于任意数,先按照对子将它取完,再看这样操作后是否还有剩余【即判断这个数原本出现的个数是奇数还是偶数】,如果有剩余,则考虑是否要取顺子,如果第二个数的数量是有奇数个且第三个数的数量不为0,则拿顺子,反之不拿顺子。

#include <iostream>
#include <cstring>

using namespace std;

const int LIM = 1e6 + 5;
int data[LIM];

int main(void) {
    int n, ans, t;
    while (~scanf("%d", &n)) {
        memset(data, 0, sizeof data);
        ans = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &t);
            data[t]++;
        }
        for (int i = 1; i <= n; i++) {
            ans += data[i] / 2;
            data[i] %= 2;
            if (data[i] && data[i + 1] && data[i + 1] % 2 && data[i + 2]) {
                ans++;
                data[i + 1]--;
                data[i + 2]--;
            }
        }
        printf("%d\n", ans);
    }
    return 0;
}