Multiple Testcases

Created by LXC on Sun Feb 11 14:53:42 2024

https://codeforces.com/problemset/problem/1342/D

ranting: 1900

tag: binary search, constructive algorithms, data structures, greedy, sortings, two pointers

problem

给予$n$个整数$m_{1,2,…,n}$，现在要将它们放进若干容器，要求：

• 在每个容器$p_j$中，对于每个数$i$（$1 \le i \le k$），大于等于$i$的数不能超过$c_i$个。

求最小所需容器数以及安排方式，保证：

• $1 \le n \le 2 \cdot 10^5$
• $1 \le k \le 2 \cdot 10^5$
• $1 \le m_i \le k$
• $n \ge c_1 \ge c_2 \ge …\ge c_k \ge 1$

输入格式：

• 第一行两个整数$n,k$。
• 第二行$n$个整数$m_{1,2,…,n}$。
• 第三行$k$个整数$c_{1,2,…,k}$。

输出格式：

• 第一行输出最小容器数$ans$（$1 \le ans \le n$）。
• 接下来输出$ans$行，第$i$行先输出一个整数$t$（$1 \le t \le n$），接下来输出$t$个整数，表示第$i-1$个容器中的元素。
• $\sum t = n$。
• $m$中的每个数恰好在某个容器中出现一次。
• 输出任意一组最优解即可。

因为$c_k \ge 1$，所以一定存在一种合法分配方式。

solution

给$m$降序排序，考虑每个$m_i$分配到哪个数组里。

对于$m_i$分配到的数组$a_j$应该满足$|a_j| < c_{m_i}$，并且要保证j尽量小以确保$|a_0|, |a_1|, |a_2|, \cdots$为降序。我们可以通过二分找到j。因此每个$m_i$的定位只需要$O(logn)$时间。

code

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}
template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}

void sol() {
	int n, k;
    cin >> n >> k;
    vector<int> m(n), c(k+1);
    for (auto& i:m) cin >> i;
    for (int i=1; i<=k; i++) {
        cin >> c[i];
    }
    int ans = 0;
    sort(m.rbegin(), m.rend());
	vector<vector<int>> g(n+1);
    for (int i:m) {
        int l = 0, r = ans;
        while (l<r) {
            int mid = l+r>>1;
            if (g[mid].size() < c[i]) r = mid;
			else l = mid+1;
        }
        g[r].push_back(i);
        ans = max(ans, r+1);
    }
    cout << ans << "\n";
    for (int i=0; i<ans; i++) {
        cout << g[i].size();
        for (auto j:g[i]) {
            cout << " " << j;
        }
        cout << "\n";
    }
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}