51nod-2510-顺子

题目：

小b有n张牌。

现在她想把牌分组，使得每组都是长度为W的顺子，即由连续W个数组成。

请问小b能做到吗？

输入

第一行输入一个数n，表示手牌张数；
第二行输入n个非负整数，表示每张牌的数字，以空格隔开；
第三行输入一个数，表示每组大小W；
其中1≤W≤n≤10000，任意牌的数字hand[i]满足0≤hand[i]≤10^9

输出

可以分组，输出“true”；
不能分组，输出“false”。

输入样例

9
1 2 3 6 2 3 4 7 8
3

输出样例

true

解法

用map记录出现的数，每次取剩下的最小的数，然后删除相应的连续的数，当出现为负数的时候，则为false

代码

#include<stdio.h>
#include<algorithm>
#include<queue>
#include<map>
using namespace std;
map<int,int> m;
int main()
{
    int n;
    scanf("%d", &n);
    int MAX = 0;
    for(int i = 0; i < n; i++){
        int a;
        scanf("%d", &a);
        MAX = max(a,MAX);
        m[a]++;
    }
    int q;
    scanf("%d", &q);
    if(n%q != 0){
        printf("false");
        return 0;
    }
    map<int,int> ::iterator it;
    while(n){
        /*for(it = m.begin(); it != m.end(); it++){
            printf("%d %d\n", it->first, it->second);
        }
        printf("\n\n");*/
        int p_1 = m.begin()->first;
        int p_2 = m.begin()->second;
        if(p_1 + q - 1 > MAX){
             printf("false");
            return 0;
        }
        for(int i = 1; i < q; i++){
            if(m.find(i+p_1) == m.end()){
                printf("false");
                return 0;
            }
            m[i+p_1] -= p_2;
            if(m[i+p_1] < 0){
                printf("false");
                return 0;
            }
            if(m[i + p_1] == 0){
                //pair<int,int> a(i+p_1,0); 
                m.erase(i+p_1);
            }
        }
        m.erase(p_1);
        n -= p_2 * q;
    }
    printf("true");
    return 0;
}