PIPIOJ 1048: PIPI的请求 map+贪心

题目：

http://39.106.164.46/problem.php?id=1048

思路：

题目要求我们把数组拆成几个恰好包含K个严格上升整数的子数组，而且要求子数组中相邻两数相差为1。 也就是说把A= {1, 1, 2, 2, 3, 3, 3, 4, 4, 5, 5, 6} ，K=4，拆成{1,2,3,5},{1,3,4,5},{2,3,4,6}这样是不行的，因为不是连续+1。
首先n必须是k的倍数。
其次，因为数组已经有序，我们可以用map记录每个数字出现的次数，然后遍历数组，当遍历到第一个数a[0]时，假设它出现的次数是cnt，那么a[0]+1,a[0]+2…a[0+k-1]这些数出现的最少次数也必须是cnt，我们让这些数出现的次数都减去cnt，若此时小于0，则说明不符合要求，若都满足要求，则继续从下一个出现次数不为0的数开始继续进行判断。

代码如下：

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<queue>
#include<cstring>
#include<vector>
#include<stack>
#include<map>
#include<set>
#define MAX 50005
#define INF 0x3f3f3f3f
typedef long long ll;
using namespace std;

int a[MAX];
int n,k;
map<int,int> mp;

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&k);
        if(n%k!=0){
            printf("NO\n");
            continue;
        }
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            mp[a[i]]++;
        }
        bool flag=true;
        for(int i=0;i<n;i++){
            if(mp[a[i]]==0){
                continue;
            }
            int cnt=mp[a[i]];
            mp[a[i]]=0;
            for(int j=a[i]+1;j<a[i]+k;j++){
                mp[j]-=cnt;
                if(mp[j]<0){
                    flag=false;
                    break;
                }
            }
            if(!flag) break;
        }
        if(!flag) printf("NO\n");
        else printf("YES\n");
        mp.clear();
    }
    return 0;
}