题解：P7912 [CSP-J 2021] 小熊的果篮

· · 题解

Luogu - P7912

考虑如何用链表维护每一个块的删除操作。

发现一个小规律：下一轮将会被删除的果子，一定是这一轮被删除的果子的下一个果子。

但仔细想发现，这一轮被删除的果子的下一个果子，下一轮不一定真的被删除，考虑如何去判断，

当满足以下两个条件的任意一个时，这一轮被删除的果子（假设为 a[x]）的下一个果子不会被删除：

  1. 当前被删除的果子的下一个果子会在当前轮结束后被合并，成为前一个块的中间部分（这样不在块头，就不会被删除）。

    判断标准：当前被删除果子的前一个和后一个相同，说明删除当前果子后，当前果子的前、后两个不同的块会被合并。

    代码：a[lst[x].pre]==a[lst[x].nxt]

  2. 当前被删除的果子的下一个果子会在当前轮被删除。

    判断标准：当前果子和下一个果子种类不一样，说明它们都是块（果篮）的开头，都会在这一轮被删掉。

    代码：a[x]!=a[lst[x].nxt]

有了上面的基础实现就很简单了。可以每一轮处理出下一轮会被删除的果子的下标，内层循环中，每次删除上一轮处理出的当前轮会被删除的数，同时根据性质继续处理当前轮可能被删除的数。

时间复杂度：这样因为每个数只会被删除一次，复杂度稳定 O(n)。

Code

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

struct Node{
    int pre, nxt; // 当前节点的前一个节点下标、后一个节点下标
};

void solve()
{
    int n;
    cin >> n;
    vector <int> a(n + 2);
    vector <Node> lst(n + 2); // 模拟双向链表的数组
    vector <int> now; // 下一轮会被删除的果子的下标

    a[0] = a[n + 1] = INT_MAX; // 避免程序判断为a[0]==a[1]，a[n]==a[n+1]
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        if(a[i] != a[i - 1]){ // 和前一个不相等，说明是当前块的块头，会被删除
            now.push_back(i);
        }
        lst[i].pre = i - 1;
        lst[i].nxt = i + 1;
    }

    lst[0].nxt = 1; // 链接lst[0]和lst[1]
    // while(!now.empty()){ // 这样写也行，如果没有下一轮要被删除的元素了，也退出循环
    while(lst[0].nxt <= n){ // 如果lst[0].nxt > n，说明链表中没有元素了，外层循环自然就结束了
        vector <int> tmp; // 处理出的下一轮会被删除的果子的下标，是now的中继数组
        for(int x : now){
            cout << x << ' ';
            lst[lst[x].nxt].pre = lst[x].pre; // 删除节点x
            lst[lst[x].pre].nxt = lst[x].nxt;
            if(a[lst[x].pre] != a[lst[x].nxt] && a[x] == a[lst[x].nxt]){ // 当前被删除的果子的下一个果子不会在当前轮结束后被合并 且 当前被删除的果子的下一个果子不会在当前轮被删除
                tmp.push_back(lst[x].nxt); // nxt下一轮会被删除
            }
        }
        cout << "\n";
        now = tmp;
    }
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

End

管理员大大辛苦啦~

谢谢大家！