题解 P7912 【小熊的果篮】

_StarBird_ · 2021-11-01 20:23:00 · 题解

看到99%的人都写了链表，我来说一个清新做法……

这题考场上想到了链表正解，结果写挂了还™没调出来，写了个暴力有70海星，CSP正解暴力区分度真是低，就因为这个导致我T3没判前导0直接65pts 哎

考完教练跟我们说了这种做法.

大概就是先记录所有苹果和橘子的位置，然后轮流取，保证取的下标递增，取完就换行再从头开始。

以样例1为例：

然后找到两坨里的最小值，这里是1，然后把1取了

接下来就取0的这一坨大于之前所取数的最小值，这里是3

大概就是这样交替取，取到不能取为止

图就变成了这样

我们发现，取的所有数就是第一轮中放到果篮里的数，所以对剩下的数这样继续做就行了。

易得在一堆取完后，另一堆会剩一个区间，一个一个输出就好了

我们发现这东西能用 set 维护，查找是 \log n 的，删除 erase 是 \log n 的，就能过了，复杂度 O(n\log n) 。

#include<bits/stdc++.h>
#define INF 200010
using namespace std;
int n;
set<int>s1,s2;//把下标扔在两个set里 
int main()
{
    scanf("%d",&n);
    s1.clear();
    s2.clear();
    int q;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&q);
        if (q) s1.insert(i);
        else s2.insert(i);
    }
    s1.insert(INF);//这里塞INF的原因是防止set空后的出错 
    s2.insert(INF);
    int nw=0;
    bool p=*s1.begin()<*s2.begin()?0:1;//这里是找两种东西最小下标的小值，p是当前删的东西 
    while(!p && s1.size()>1 || p && s2.size()>1)//因为有个INF，所以size要>1 
        if (!p)
        {
            nw=*s1.upper_bound(nw);//upper_bound找下一个 
            if (nw==INF)//找不完了就从头开始 
            {
                nw=0;
                p=*s1.begin()<*s2.begin()?0:1;//p要重新选 
                puts("");
                continue;
            }
            printf("%d ",nw);//取了，输出，删除 
            s1.erase(nw);
            p=!p;//取另外一坨 
        }
        else//同上 
        {
            nw=*s2.upper_bound(nw);
            if (nw==INF)
            {
                nw=0;
                p=*s1.begin()<*s2.begin()?0:1;
                puts("");
                continue;
            }
            printf("%d ",nw);
            s2.erase(nw);
            p=!p;
        }
    puts("");//最后一个果篮是没换行的 
    while(s1.size()>1) printf("%d\n",*s1.begin()),s1.erase(*s1.begin());//一坨取完以后，另外一堆是一个区间，一行一行输出 
    while(s2.size()>1) printf("%d\n",*s2.begin()),s2.erase(*s2.begin());//同上 
    return 0;
}

其他几点：

1. 这里塞INF是因为不塞INF而判end的话，后面再找upper_bound会找到end会炸
2. 不能删到底就从头开始，因为可能另外一堆还有东西要删
3. 这个做法在水果种类多的情况下前途很好，多开几个set轮流取就好了

大概就是这样了叭~