题解 | #乐团派对#

贪心做法（含正确性分析，欢迎 Hack）

首先将每一个乐手预处理成一个集，之后我们考虑两两合并获取最大可能集合数量。

struct SizeMaxSet
{
    int size;
    int maxs;
    bool check() { return maxs <= size; }
};

我们处理输入：

int n;
cin >> n;
vector<int> vi(n);
for (int i = 0; i < n; i++)
{
    cin >> vi[i];
}
for (int i : vi)
{
    SizeMaxSet sm;
    sm.size = 1;				// 初始大小为 1
    sm.maxs = i;				// 当前集合最大值为 i
    if (sm.check())
    {
        pqtrue.push(sm);		// pqtrue 表示满足的集合的优先队列
    }
    else
    {
        pq.push(sm);			// pq 表示暂未满足的优先队列
    }
}

Sample

初始情况下，我们以 $n=12,a[]=\{1,1,1,1,1,6,6,6,6,6,6,6\}$ 为例，那么我们在进行操作的时候，所有为 1 的都被加入优先队列，为了方便读者理解，红色为在 pqtrue 队列中，蓝色表示在 pq 队列中。

alt

接下来合成 pq 队列中的元素，贪心地将其合并：

alt

合并完毕后，结果只剩一个 6，无法继续从 pq 合并了，那么我们从 pqtrue 选取 size 最大的优先合并，如果不满足，继续从堆顶取出合并。这里我们合并为如下图所示的结果：

alt

最后输出 pqtrue.size()

正确性分析

如下图所示，我们进行最大堆排序，使用 pq 命名，那么如果要满足 $x_{12}=n$ 的要求，则需要从优先队列贪心选取最大的 $n$ 个元素合并来满足条件，这样可以保证剩余数字所需要的集合 size 尽可能小，这样分割数会尽可能大。

alt

选取正好满足即 $maxs=size$ 的情况加入优先队列 pqtrue 准备优先合并 size 较大的集合，因为同样是合并 1 个集合，size 较大的集合可以为不满足条件的集合增加更多的乐手。

考虑 $x_0\sim x_5$ 的集合，也是优先从 $x_5$ 开始合并 $x_5$ 个集合，共有如下的情况：

满足条件 $maxs=size$ 时正好是全部合并，直接推入 pqtrue 并输出 pqtrue.size()，退出程序，此时一定是正确答案。
满足条件 $maxs=size$ 时并没有全部合并，推入 pqtrue 继续缩小区间执行合并，这样满足 pq 队列里面留下的一定是没法再继续向下分的 $\color{red}1$ 个集合。
剩下的所有都合并的时候都不能满足 $maxs\leqslant size$ 从 pqtrue 弹出最大 size 的与其合并，这样在总集合数量 $-1$ 的情况下尽可能让 $size$ 超过 $maxs$ ，这一定是最优策略。
如果每次按照 3 的最优策略合并下来满足 $maxs\leqslant size$ ，停止从 pqtrue 弹出，将当前合并结果推入优先队列，输出 pqtrue.size() 即答案。
如果全部合并下来都不满足 $maxs\leqslant size$ ，输出 $-1$ 。

下面是合并的过程：

SizeMaxSet sm;
sm.size = p1.size + p2.size;
sm.maxs = max(p1.maxs, p2.maxs);

优先队列的定义：

auto cmp = [](const SizeMaxSet &a, const SizeMaxSet &b)
{
  if (a.maxs > a.size && a.maxs > b.maxs)
  {
    return false;
  }
  if (b.maxs > b.size)
  {
    return true;
  }
  if (a.size == b.size)
  {
    return a.maxs < b.maxs;
  }
  return a.size < b.size;
};
sort(vi.begin(), vi.end());
priority_queue<SizeMaxSet, vector<SizeMaxSet>, decltype(cmp)> pq(cmp);
auto cmp2 = [](const SizeMaxSet &a, const SizeMaxSet &b) { return a.size < b.size; };
priority_queue<SizeMaxSet, vector<SizeMaxSet>, decltype(cmp2)> pqtrue(cmp2);

AC Code

#include <bits/stdc++.h>
using namespace std;

struct SizeMaxSet
{
    int size;
    int maxs;
    bool check() { return maxs <= size; }
};
int main(int argc, char *argv[])
{
    int n;
    cin >> n;
    vector<int> vi(n);
    for (int i = 0; i < n; i++)
    {
        cin >> vi[i];
    }
    auto cmp = [](const SizeMaxSet &a, const SizeMaxSet &b)
    {
        if (a.maxs > a.size && a.maxs > b.maxs)
        {
            return false;
        }
        if (b.maxs > b.size)
        {
            return true;
        }
        if (a.size == b.size)
        {
            return a.maxs < b.maxs;
        }
        return a.size < b.size;
    };
    sort(vi.begin(), vi.end());
    priority_queue<SizeMaxSet, vector<SizeMaxSet>, decltype(cmp)> pq(cmp);
    auto cmp2 = [](const SizeMaxSet &a, const SizeMaxSet &b) { return a.size < b.size; };
    priority_queue<SizeMaxSet, vector<SizeMaxSet>, decltype(cmp2)> pqtrue(cmp2);

    for (int i : vi)
    {
        SizeMaxSet sm;
        sm.size = 1;
        sm.maxs = i;
        if (sm.check())
        {
            pqtrue.push(sm);
        }
        else
        {
            pq.push(sm);
        }
    }
    while (pq.top().maxs > pq.top().size && pq.size() != 1 && pq.size() != 0)
    {
        auto p1 = pq.top();
        pq.pop();
        auto p2 = pq.top();
        pq.pop();
        SizeMaxSet sm;
        sm.size = p1.size + p2.size;
        sm.maxs = max(p1.maxs, p2.maxs);
        if (sm.check())
        {
            pqtrue.push(sm);
        }
        else
        {
            pq.push(sm);
        }
    }
    if (pq.size() == 1)
    {
        auto top = pq.top();
        if (top.check())
        {
            pqtrue.push(top);
            cout << pqtrue.size();
            return 0;
        }

        bool ok = false;
        while (!pqtrue.empty())
        {
            top.size += pqtrue.top().size;
            top.maxs = max(pqtrue.top().maxs, top.maxs);
            pqtrue.pop();
            if (top.check())
            {
                pqtrue.push(top);
                ok = true;
                break;
            }
        }
        if (!ok)
        {
            cout << -1;
        }
        else
        {
            cout << pqtrue.size();
        }
    }
    else
    {
        cout << pqtrue.size();
    }
    return 0;
}