CF1342D

FiraCode · 2022-07-27 11:02:03 · 题解

题解思路：

我们对于 c 相同的看成一个数。 那么我们倒着扫描，那么只要能放就放就可以了。

AC CODE：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 5;
int n, k, cnt;
int a[N], b[N], p[N], fp[N], num[N];
vector<int> zz[N];
inline void init()
{
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i)
    {
        int x;
        cin >> x;
        ++num[x];
    }
    for (int i = 1; i <= k; ++i)
    {
        int x;
        cin >> x;
        if (!p[x])
            p[x] = ++cnt, fp[cnt] = x;
        a[cnt] += num[i];
        while (num[i]--)
            zz[cnt].push_back(i);
    }
    for (int i = 1; i <= n; ++i)
        b[i] = fp[i] - fp[i + 1];
    int x = 0;
    for (int i = cnt; i >= 1; --i)
    {
        if (!a[i])
            x += b[i];
        else
            b[i] += x, x = 0;
    }
}
int main()
{
    init();
    vector<vector<int>> ans;
    vector<pair<int, int>> now, last;
    for (int i = cnt; i >= 1; --i)
    {
        if (!a[i])
            continue;
        last.push_back({i, a[i]});
    }
    while (!last.empty())
    {
        int val = 0, z = 0;
        vector<int> res;
        for (auto &x : last)
        {
            int id = x.first, w = x.second;
            val += b[id];
            b[id] += z;
            int mi = min(x.second, val);
            w -= mi;
            val -= mi;
            while (mi--)
                res.push_back(id);
            if (w)
                now.push_back({id, w}), z = 0;
            else
                z = b[id];
        }
        ans.push_back(res);
        last = now;
        now.clear();
    }
    cout << ans.size() << '\n';
    for (auto &x : ans)
    {
        cout << x.size() << ' ';
        for (auto y : x)
        {
            cout << zz[y].back() << ' ';
            zz[y].pop_back();
        }
        cout << '\n';
    }
    return 0;
}