2021 小熊的果篮 · 方案一每轮扫一遍

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 4/5 · 共 1149 字

从头扫到尾找每一块的块头

2021
模拟

正文

// CSP-J 2021 复赛 T4 · 小熊的果篮
// 原题：https://oj.yecheng.tv/p/CSPJ2021D
// 题意：一排水果，连续相同的算一个「块」。每一轮把每个块最左边的水果同时挑出来，
// 组成一个果篮；挑走之后块可能会合并。输出每个果篮里的水果编号。
//
// 方案一 · 每轮整排扫一遍找块头（直观，n 大时会超时）
// 用一个 gone 数组记哪些已经被挑走了。每一轮从头扫到尾，
// 只要当前水果的种类和上一个没被挑走的水果不同，它就是这一块的块头。
// 扫完把块头一起挑走、一起输出，进入下一轮。
// 每轮都要扫全长，轮数最多 n 轮，最坏 O(n^2)，n = 2e5 时来不及。

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

int main() {
    freopen("fruit.in", "r", stdin);
    freopen("fruit.out", "w", stdout);

    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    vector<bool> gone(n + 1, false);
    int left = n;
    while (left > 0) {
        vector<int> out;
        int prevType = -1;
        for (int i = 1; i <= n; i++) {
            if (gone[i]) continue;
            if (a[i] != prevType) {          // 种类变了，说明新的一块开始了
                out.push_back(i);
                prevType = a[i];
            }
        }
        for (int i : out) {
            gone[i] = true;
            left--;
        }
        for (size_t k = 0; k < out.size(); k++) {
            cout << out[k] << (k + 1 == out.size() ? '\n' : ' ');
        }
    }
    return 0;
}

2021 小熊的果篮 · 方案一 每轮扫一遍

正文

CSP-J 标程 · 复赛真题的其它内容

2021 小熊的果篮 · 方案一每轮扫一遍