D.Multiple Testcases(併記)

http://codeforces.com/contest/1342/problem/D
タイトル:
n個の数∈[1,k]in[1,k]∈[1,k]を与え,最小の集合に分ける.各集合がi∈[1,k]iin[1,k]i∈[1,k]i∈[1,k]以上の数を満たす最大c i c_i ci個.
解析:
私たちは欲張って集合を塞いで、大きいから小さいまで.
各数i i iについて,我々は2つの状況に分けた.

i i iの数が足りなければ、次はこの点にはならないので、f a[i]=i−1 fa[i]=i−1 fa[i]=i−1 fa[i]=1となる.そして今i−1 i−1 i−1を探しに行きます.

現在の数がc i c_に達した場合i ciは、すぐにi i iより小さいj j jを探して、c j>c i c_j>c_i cj​>ci​

初めてこのように使って集を调べて、今思ったのは比较的に疲れます...
コード:

/*
 *  Author : Jk_Chen
 *    Date : 2020-04-26-23.02.11
 */
#include
using namespace std;
#define LL long long
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);i++)
#define per(i,a,b) for(int i=(int)(a);i>=(int)(b);i--)
#define mmm(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define pill pair
#define fi first
#define se second
void test(){cerr<<"
";}
template<typename T,typename... Args>void test(T x,Args... args){cerr<<"> "<<x<<" ";test(args...);}
const LL mod=1e9+7;
const int maxn=2e5+9;
const int inf=0x3f3f3f3f;
LL rd(){ LL ans=0; char last=' ',ch=getchar();
    while(!(ch>='0' && ch<='9'))last=ch,ch=getchar();
    while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();
    if(last=='-')ans=-ans; return ans;
}
#define rd rd()
/*_________________________________________________________begin*/

struct Uni{
    int num;
    int tmp[maxn];
    int operator[](int idx)const{
        return tmp[idx];
    }
    int& operator[](int idx){
        return tmp[idx];
    }
    void push(int x){
        tmp[++num]=x;
    }
    void init(){
        sort(tmp+1,tmp+1+num);
        num=unique(tmp+1,tmp+1+num)-tmp-1;
    }
    int idx(int val){
        return lower_bound(tmp+1,tmp+1+num,val)-tmp;
    }
}U;
/*_________________________________________________________unique*/


vector<int>V[maxn];
int c[maxn];
int ct[maxn];

int nex[maxn];
int fa[maxn];
int fin(int p){return fa[p]==p?p:fa[p]=fin(fa[p]); }

int main(){
    int n=rd,k=rd;
    rep(i,1,n){
        int a=rd;
        U.push(a);
        ct[a]++;
    }
    rep(i,1,k){
        c[i]=rd;
    }
    U.init();
    rep(i,1,U.num){
        c[i]=c[U.tmp[i]];
    }
    c[0]=1e9;
    rep(i,1,U.num){
        if(c[i]==c[i-1])nex[i]=nex[i-1];
        else nex[i]=i-1;
        fa[i]=i;
    }

    int res=n;
    int id=0;
    while(res){
        id++;
        int p=fin(U.num);
        while(p){
            while(p&&V[id].size()<c[p]&&ct[U.tmp[p]]){
                V[id].pb(U.tmp[p]);
                ct[U.tmp[p]]--;
                res--;
                if(ct[U.tmp[p]]==0){
                    fa[p]=p-1;
                }
            }
            if(V[id].size()>=c[p])
                p=fin(nex[p]);
            else
                p=fin(p-1);
        }
    }
    printf("%d
",id);
    rep(i,1,id){
        printf("%d ",V[i].size());
        for(auto P:V[i]){
            printf("%d ",P);
        }
        puts("");
    }
    return 0;
}

/*_________________________________________________________end*/