复赛四:小熊的果篮

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**************************************************************** 
 * Description: 2021年CSP-J 复赛第四题，小熊胡果篮(fruit)
   主要思路是利用一个标记 flag 来记录当前被挑选的水果种类，并在挑选完一个果篮后更新该标记，
   以确保每次挑选时不会重复挑选同一块中的水果。
   该算法的时间复杂度是𝑂(𝑛^2)
 * Author: Alex Li
 * Date: 2023-10-16 14:33:09
 * LastEditTime: 2024-08-05 20:22:13
****************************************************************/
#include <iostream>
using namespace std;

// 定义全局数组 a，用于存储每个水果的种类，n 表示水果的数量，cnt 用于记录已经挑出的水果数量
int a[200010], n, cnt;

int main() {
    // 读取水果的数量
    cin >> n;
    
    // 读取每个水果的种类，1 代表苹果，0 代表桔子
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 当已经挑出的水果数量少于总数量时，继续挑选
    while (cnt < n) {
        int flag = 2; // 初始 flag 值设置为 2，表示当前未选中的水果种类（1 或 0）
        
        // 遍历所有水果
        for (int i = 1; i <= n; i++) {
            // 如果当前水果还未被挑出且其种类与上一次选中的不同
            if (a[i] != -1 && a[i] != flag) {
                flag = a[i]; // 更新 flag 为当前水果的种类
                a[i] = -1; // 将当前水果标记为已挑出
                cout << i << ' '; // 输出当前水果的编号
                cnt++; // 已挑出的水果数量加一
            }
        }
        
        // 输出当前果篮的所有水果编号后换行
        cout << endl;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

/**************************************************************** 
 * Description: 2021 CSP-J 复赛第4题，小熊的果蓝
 利用结构体存储单个块，并用队列存储所有块
 * Author: Alex Li
 * Date: 2023-10-16 14:55:45
 * LastEditTime: 2024-08-05 20:37:10
****************************************************************/
#include <iostream>
#include <queue>
using namespace std;

// 定义节点结构体，用于存储块的左右边界和块的水果种类
struct node {
    int L, R, num;
};

int n, t, cnt;
queue<node> q; // 定义队列用于存储所有块

int main() {
    int flag = 2; // 初始 flag 值设置为 2，表示当前未选中的水果种类（1 或 0）
    cin >> n;
    
    // 读取每个水果的种类，并根据块的定义将块加入队列
    for (int i = 1; i <= n; i++) {
        cin >> t;
        if (t != flag) {
            q.push((node){i, i, t}); // 如果当前水果与前一个不同，则新建一个块
            flag = t;
        } else {
            q.back().R = i; // 如果相同，则延伸当前块的右边界
        }
    }
    
    // 当队列不为空时，进行挑选操作
    while (!q.empty()) {
        int k = q.size(); // 记录当前队列的大小，即当前的块数
        int flag = 2; // 重置 flag
        
        // 遍历当前所有块
        for (int i = 1; i <= k; i++) {
            // 如果当前块的水果种类与上一次选中的不同
            if (q.front().num != flag) {
                cout << q.front().L << ' '; // 输出块的最左边水果编号
                q.front().L++; // 将块的左边界右移
                flag = q.front().num; // 更新 flag 为当前块的种类
            }
            
            // 如果块的左边界未超过右边界，将块重新入队
            if (q.front().L <= q.front().R)
                q.push(q.front());
            q.pop(); // 移除当前块
        }
        
        // 输出当前果篮的所有水果编号后换行
        cout << endl;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85

/**************************************************************** 
 * Description: 2021 CSP-J 复赛第四题，小熊的果篮
 两个队列，合并队列
 * Author: Alex Li
 * Date: 2023-10-16 14:55:45
 * LaLRitTime: 2023-10-17 05:44:49
****************************************************************/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

struct block { // 定义块结构体
    int L, R, th; // L: 块的左边界, R: 块的右边界, th: 块的水果种类
} f, x, ad;

int n, cnt, t[200001];
queue<block> q, q2; // 定义两个队列，一个用于处理块，一个用于合并块
bool used[200001]; // 记录每个位置的水果是否已被取出

int main() {
    cin >> n;
    
    // 读取每个水果的种类
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
    }
    
    t[n + 1] = !t[n]; // 设置一个哨兵，用于标记最后一个块的结束
    
    // 合并相同水果的块
    for (int i = 2, si = 1; i <= n + 1; i++) {
        if (t[i] != t[i - 1]) {
            q.push((block){si, i - 1, t[i - 1]}); // 将块推入队列
            si = i; // 更新下一个块的起始位置
        }
    }
    
    cnt = n; // 初始化剩余水果数量
    
    while (cnt) {
        while (q.size()) {
            f = q.front(); // 取出队列中的第一个块
            q.pop();
            
            // 移动块的左边界，跳过已取出的水果
            while (used[f.L] && f.L <= f.R) {
                f.L++;
            }
            
            if (f.L > f.R) continue; // 如果块已经空了，跳过
            
            cout << f.L << ' '; // 输出当前块的第一个水果编号
            cnt--; // 减少剩余水果数量
            used[f.L] = 1; // 标记当前水果已取出
            
            if (f.R == f.L) continue; // 如果这个块只有一个水果，继续
            
            f.L++; // 移动块的左边界
            q2.push(f); // 将块存入临时队列 q2
        }
        
        cout << endl;
        
        // 合并相邻相同种类的块
        while (q2.size()) {
            ad = q2.front();
            q2.pop();
            
            while (q2.size()) {
                x = q2.front();
                if (x.th == ad.th) { // 如果相邻块的种类相同，合并块
                    ad.R = x.R;
                    q2.pop();
                } else {
                    break;
                }
            }
            
            q.push(ad); // 将合并后的块推入主队列
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

/**************************************************************** 
 * Description: 2021 CSP-J 复赛第四题目 链表的方式
 * Author: Alex Li
 * Date: 2024-08-05 20:44:27
 * LastEditTime: 2024-08-05 22:53:13
****************************************************************/
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 2e5+10; // 定义最大水果数量

struct Node {
    int prev; // 前一个节点的索引
    int val;  // 当前节点的值
    int next; // 后一个节点的索引
};

int n; // 水果数量

int fruit[MAXN]; // 用于存储每个水果的种类
Node headList[MAXN]; // 用于存储块的头节点, val 字段表示水果的位置
Node fruitList[MAXN]; // 用于存储所有水果的双向链表节点,val表示块的头位置。
int cc; // 用于记录当前块的数量

// 函数用于取出一个水果
void EatOne(int pos) { //pos=position 位置
    int prev = fruitList[pos].prev;
    int next = fruitList[pos].next;
    fruitList[prev].next = next; // 更新前一个节点的 next 指向
    fruitList[next].prev = prev; // 更新后一个节点的 prev 指向
    cout<<pos<<' '; // 打印当前取出的水果位置
}

// 函数用于删除一个块的头节点
void Del(int pos) {
    int prev = headList[pos].prev;
    int next = headList[pos].next;
    headList[prev].next = next; // 更新前一个头节点的 next 指向
    headList[next].prev = prev; // 更新后一个头节点的 prev 指向
}

// 主函数用于处理每次取水果操作
void getFruit() {
    int solo = headList[0].next; // 从第一个块开始
    int nowcolor = fruit[headList[solo].val]; // 当前块的水果种类
    while (solo != cc + 1) { // 遍历所有块
        if (fruit[headList[solo].val] != nowcolor) { // 如果当前块的水果种类不同
            Del(solo); // 删除当前块的头节点
            solo = headList[solo].next; // 移动到下一个块
            continue;
        }
        EatOne(headList[solo].val); // 取出当前块的一个水果
        headList[solo].val = fruitList[headList[solo].val].next; // 更新块的头节点
        if (fruit[headList[solo].val] != nowcolor) { // 如果更新后的块的水果种类不同
            Del(solo); // 删除当前块的头节点
        }
        solo = headList[solo].next; // 移动到下一个块
        nowcolor ^= 1; // 切换水果种类（0 和 1 之间切换）
    }
    cout<<'\n'; // 打印换行
}

int main() {
    cin>>n; // 读取水果数量
    fruitList[0].next = 1; // 初始化双向链表的起点
    for (int i = 1; i <= n; i++) { //从1开始
        cin>>fruit[i]; // 读取每个水果的种类
        fruitList[i].prev = i - 1; // 初始化前一个节点的索引
        fruitList[i].next = i + 1; // 初始化后一个节点的索引
    }
    fruit[0] = 2; // 设置哨兵值
    fruit[n+1] = 2; // 设置哨兵值
    headList[0].next = 1; // 初始化头节点链表的起点
    for (int i = 1; i <= n; i++) {
        if (fruit[i] != fruit[i - 1]) { // 如果当前水果种类与前一个不同
            cc++; // 增加块的数量
            headList[cc].prev = cc - 1; // 初始化前一个块的索引
            headList[cc].next = cc + 1; // 初始化下一个块的索引
            headList[cc].val = i; // 初始化当前块的值
        }
    }
    while (fruitList[0].next != n + 1) { // 当还有水果未取出时
        getFruit(); // 进行一次取水果操作
    }
    return 0;
}