HDU 6188 Duizi and Shunzi 贪心思维

　　题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=6188

　　题目描述：就是一副扑克牌，可以打顺子，可以打对子，问怎样顺子和对子的总数能够最多

　　解题思路：贪心，对于一种牌先向前找看看是否能够组成顺子，如果能组成顺子就出顺子，然后就将本身剩余的全部当做对子，在这里我们需要对前两个进行预处理，将对子全部拿走，所以前两个只能剩一个或者0个，然后从第三个开始贪心，这样当前处理的牌前两个一定是0 个或者 1 个，现在证明这个算法的正确性，总体来讲对子是要比顺子优的，只有一种情况顺子比对子优，那就是一个对子恰好是两个顺子的头和尾，如 123 345，这样优先顺子要比对子优，而我们正是特殊处理了这种情况，所以保证了算法的正确性

　　代码：

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <stack>
#include <deque>
#include <map>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define mem0(a) memset(a,0,sizeof(a))
#define sca(x) scanf("%d",&x)
#define de printf("=======
")
typedef long long ll;
using namespace std;

const int maxn = 1e6+10;
int cnt[maxn];

int main() {
    int n;
    while( sca(n) == 1 ) {
        mem0(cnt);
        for( int i = 1; i <= n; i++ ) {
            int num;
            sca(num);
            cnt[num]++;
        }
        ll ans = 0;
        for( int i = 1; i <= n; i++ ) {
            if( i == 1 || i == 2 ) {
                ans += cnt[i] / 2;
                cnt[i] -= 2 * (cnt[i]/2);
             }
            else {
                if( cnt[i-1] && cnt[i-2] && cnt[i] ) {
                    ans ++;
                    cnt[i-1]--, cnt[i-2]--, cnt[i]--;
                }
                ans += cnt[i] / 2;
                cnt[i] -= 2 * (cnt[i]/2);
            }
        }
        printf( "%lld
", ans );
    }
    return 0;
}

View Code

　　思考：这是我第一次证明算法的正确性，感觉好爽啊......另外感觉这场比赛打得好爽啊......可能是因为题简单/.......把那两道题补了吧....因为健身我每天失去了两个半小时时间，所以就更需要我专心的去写每一段代码

HDU 6188 Duizi and Shunzi 贪心 思维

HDU 6188 Duizi and Shunzi 贪心思维