题解：AT_abc140_f [ABC140F] Many Slimes

· · 题解

思路

按照题意，我们很好想到一种特殊情况，就是当前有两个最大值，那么肯定是不合法的，有其中一个最大值无法被生出来。

按照贪心的思想，我们肯定要对数组排个序，这样才能每次用大的史莱姆去生成小的史莱姆对吧。

每一个大史莱姆都可以生成一个小史莱姆，我们假设当前生成的小史莱姆是 A。那么 A 肯定是第一个比大史莱姆小的史莱姆。这样才更优。如果有其它的小史莱姆需要生成，肯定小于或者等于 A，肯定不会大于 A，这样就可以用别的更小的史莱姆去生。而不会出现这种情况，之前大史莱姆生成了一个最小的史莱姆，但是集合中的某个史莱姆太大了，只能用这个大史莱姆生成，但是大史莱姆没有去生成，导致这个史莱姆没有被生成。

不过生成的这些小史莱姆要按照题目给的集合去生成。

既然要按照题目所给的集合去生成，我们按照题意模拟即可。

我这里用了三个 multiset，第一个不妨称作 s，第二个称作 s2，第三个之后再讲。

s 代表当前已经生成了的史莱姆集合，s2 代表题目给定的集合，也就是还需要生成的史莱姆集合。每次生成一个史莱姆，就在 s 中加入史莱姆，s2 删去史莱姆就好。

但是这样操作会让 s 集合不断更新，导致循环出问题，所以我们开一个辅助集合 t，这样把加入的史莱姆先加入在 t 中，最后再把 t 覆盖给 s 就行了。

这样的操作一共会进行 n 次，简单模拟下就可以知道为什么了，这里不过多赘述。

如何去找第一个比自己要小的史莱姆？可以二分查找，因为 a_i 排过序后，有单调性，且维护的集合带有自动排序的功能，也有单调性。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=270005;

int n, a[N], cnt=0;
multiset<int> s, t, s2;
multiset<int>::iterator it, it2;
bool cmp(int a, int b)
{
    return a>b;
}
int main()
{
    scanf("%d", &n);
    for (int i=1; i<=(1<<n); i++) scanf("%d", &a[i]);
    sort(a+1, a+1+(1<<n), cmp);

    if (a[1]==a[2])
    {
        printf("No");
        return 0;
    }

    s.insert(a[1]);
    t.insert(a[1]);
    for (int i=2; i<=(1<<n); i++) s2.insert(a[i]);

    for (int i=1; i<=n; i++)
    {
        for (it=s.begin(); it!=s.end(); it++)
        {
            it2=s2.lower_bound((*it));

            if (it2==s2.begin()) //没有史莱姆可以生成了
            {
                printf("No");
                return 0;
            }

            it2--;
            t.insert((*it2));
            s2.erase(it2);
        }
        s=t;

    /*  for (it=s.begin(); it!=s.end(); it++) printf("%d ", (*it));
        puts("");*/
    }
    printf("Yes");

    return 0;
}