数据结构作业题解05

数据结构作业题解05

exdoubled Lv4
  2025-10-23 17:00 2025-10-23 17:00 Created   2025-12-27 20:23:47 2025-12-27 20:23:47 Updated    4.9k Words  22 Mins  

A. 血魔训练 II

题目描述

ZZR 在玩 DOTA2 中的血魔角色。血魔的技能是：每当他击杀一个英雄单位后，他能回复该英雄生命值上限百分比的血量。

假设 ZZR 有 \(x\) 滴血，现在有 \(n\) 个敌方英雄。ZZR 杀死每个敌方英雄需要损失 \(a_i\) 滴血，但是当他杀死该英雄之后能够恢复 \(b_i\) 滴血。

当 ZZR 血量小于或等于 0 时 ZZR 就死亡，训练结束。

ZZR 想要击杀尽可能多的敌方英雄，请问他在保证自己不死亡的情况下，能否击杀所有英雄。

输入格式

第一行包括两个数 \(n, x\)，分别表示 \(n\) 个英雄和 \(x\) 滴血。

第二行包括 \(n\) 个数 \(a_1, \cdots, a_n\)，表示 ZZR 击杀每个英雄所需消耗的血量。

第三行包括 \(n\) 个数 \(b_1, \cdots, b_n\)，表示 ZZR 击杀每个英雄恢复的血量。

输出格式

“YES” 或 “NO”，表示能否击杀所有英雄。

样例

样例 1

输入：

1
2
3
4 10
12 11 2 3
10 2 5 4

输出：

1
YES

样例 2

输入：

1
2
3
3 10
6 8 7
2 6 4

输出：

1
NO

样例 3

输入：

1
2
3
2 14
12 11
2 10

输出：

1
YES

数据范围

\(1 \leq n \leq 10^5\)，\(1 \leq x, a_i, b_i \leq 10^9\)。

思路与题解

虽然一眼看出来是贪心，但是贪心思路卡了很久…

特别感谢某同学提供了下面的贪心策略和正确性证明

设收益为 \(b-a\) 的值，如果为正，不难发现需要按照 \(a\) 的值排序，如果不能打败 \(a_i\) ，后面收益为正的 \(a_j\) 一定都打不过，因为剩下的都是收益为负或者收益为正但代价比 \(a_i\) 大

考虑收益为正的已经按照 \(a\) 的值从小到大排列好

假设收益为负的排列是一个合理的排列

相邻 \(i \to j\) 可行当且仅当 \(x > a_i\) 且 \(x - (a_i - b_i) > a_j\)，从而 \(x > a_j\)。 交换成 \(j \to i\) 需 \(x - (a_j - b_j) > a_i\) 由 \(x - (a_i - b_i) > a_j\) 得 \(x > a_j + (a_i - b_i)\)

构造一个新排列

当 \(b_j < b_i\) 排列不变

当 \(b_j \ge b_i\) 时，\(a_j + (a_i - b_i) \ge a_i + (a_j - b_j)\)，故\(x > a_i + (a_j - b_j) \iff x - (a_j - b_j) > a_i\)，交换后仍可行，新排列就把这两个元素交换

那么一个合理（有解）的排列一定可以构造成一个回血量 \(b\) 是降序的排列

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
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

using ll = long long;

struct Node {
    ll a;
    ll b;
};

bool cmp1(const Node &x, const Node &y) {
    if (x.b != y.b) return x.b > y.b;
    else return x.a > y.a;
}

bool cmp2(const Node &x, const Node &y) {
    return x.a < y.a;
}


int main() {
    int n;
    ll x;
    cin >> n >> x;
    vector<Node> v(n);
    for (int i = 0; i < n; ++i) {
        cin >> v[i].a;
    }
    for (int i = 0; i < n; ++i) {
        cin >> v[i].b;
    }
    vector<Node> pos;
    vector<Node> neg;
    for (int i = 0; i < n; ++i) {
        if (v[i].b > v[i].a) pos.push_back(v[i]);
        else neg.push_back(v[i]);
    }

    sort(pos.begin(), pos.end(), cmp2);
    for (int i = 0; i < pos.size(); ++i) {
        if (x > pos[i].a) {
            x += pos[i].b - pos[i].a;
        } else {
            cout << "NO";
            return 0;
        }
    }

    sort(neg.begin(), neg.end(), cmp1);
    for (int i = 0; i < neg.size(); ++i) {
        if (x > neg[i].a) {
            x += neg[i].b - neg[i].a;
        } else {
            cout << "NO";
            return 0;
        }
    }
    cout << "YES";
    return 0;
}

B. 逆序对

题目描述

ZZR 有一个序列 \(a_1, a_2, \cdots, a_n\)，他允许最多进行 \(k\) 次操作，每次操作交换两个相邻元素。

求经过交换后的序列中最少还有多少逆序对。

逆序对指的是二元组 \((i, j)\)，其满足 \(i < j\) 且 \(a_i > a_j\)。

输入格式

第一行包含两个数 \(n, k\)，表示序列长度和交换两个相邻元素的次数上限。

第二行有 \(n\) 个数，表示序列 \(a_1, a_2, \cdots, a_n\)。

输出格式

一个数表示最少的逆序对的数量。

样例

样例 1

输入：

1
2
3 1
2 2 1

输出：

1
1

样例 2

输入：

1
2
3 0
2 2 1

输出：

1
2

数据范围

\(1 \leq n \leq 10^5, 0 \leq k \leq 10^9, 1 \leq a_i \leq 10^9\)。

思路与题解

其实就是统计逆序对有多少对，用归并的方法，还有树状数组和线段树的方法，实现复杂，在此不提

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
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

ll merge(vector<int>& v, int l, int mid, int r) {
    vector<int> temp;
    int i = l, j = mid + 1;
    ll count = 0;
    while (i <= mid && j <= r) {
        if (v[i] <= v[j]) {
            temp.push_back(v[i++]);
        } else {
            temp.push_back(v[j++]);
            count += mid - i + 1;
        }
    }
    while (i <= mid) {
        temp.push_back(v[i++]);
    }

    while (j <= r) {
        temp.push_back(v[j++]);
    }

    for (int p = 0; p < temp.size(); ++p) {
        v[l + p] = temp[p];
    }
    return count;
}

ll mergeSort(vector<int> &v, int l, int r) {
    ll count = 0;
    if (l < r) {
        int mid = l + (r - l) / 2;
        count += mergeSort(v, l, mid);
        count += mergeSort(v, mid + 1, r);
        count += merge(v, l, mid, r);
    }
    return count;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    long long inv = mergeSort(a, 0, n - 1);
    cout << max(0LL, inv - k) << endl;
    return 0;
}

C. 你美还是我美

题目描述

Y 看了 B 站的抽象视频，感到非常开心。所以他决定举办美丽值对抗赛来调剂同学们枯燥的军训生活。

已知同学分成两组，美丽值分别为 \(a_1, a_2, \cdots, a_n\) 和 \(b_1, b_2, \cdots, b_m\)。

美丽值为 \(x\) 和 \(y\) 的两名同学进行对抗会产生 \(|x - y|\) 颗美丽爱心，求两组同学两两对抗能产生多少美丽爱心。即求 \[\sum_{i=1}^n \sum_{j=1}^m |a_i - b_j|\]

输入格式

第一行两个整数 \(n, m\) 分别表示两组同学的数量。

第二行 \(n\) 个正整数表示 \(a_1, a_2, \cdots, a_n\)。

第三行 \(m\) 个正整数表示 \(b_1, b_2, \cdots, b_m\)。

输出格式

一行一个数表示美丽爱心数量。

样例

输入：

1
2
3
3 2
1 2 3
1 10

输出：

1
27

数据范围

\(1 \leq n, m \leq 2 \times 10^5, 1 \leq a_i, b_i \leq 10^8\)。

思路与题解

考虑每个元素对和的贡献：每一个 \(b_i\) 考虑在 \(a[n]\) 中的位置，比 \(b_i\) 小的 \(b_i\) 贡献为正，否则贡献为负，统计 \(b_i\) 的贡献次数，再同理统计 \(a_i\) 的加起来即可

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    vector<long long> mpa(n, 0), mpb(m, 0);


    for (int i = 0; i < m; ++i) {
        long long countLeq = lower_bound(a.begin(), a.end(), b[i]) - a.begin();
        long long countGeq = a.end() - upper_bound(a.begin(), a.end(), b[i]);
        mpb[i] = countLeq - countGeq;
    }

    for (int i = 0; i < n; ++i) {
        long long countLeq = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
        long long countGeq = b.end() - upper_bound(b.begin(), b.end(), a[i]);
        mpa[i] = countLeq - countGeq;
    }

    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans += mpa[i] * a[i];
    }
    for (int i = 0; i < m; ++i) {
        ans += mpb[i] * b[i];
    }
    cout << ans;

    return 0;
}

D. 新·合并果子

题目描述

乔治家后面有 \(n\) 堆果子，第 \(i\) 堆中有 \(a_i\) 个果子。

乔治想把这些果子合并成一堆。他仅可以执行以下操作：

选中两堆果子，不妨设其中一堆有 \(x\) 个果子，另一堆有 \(y\) 个果子，将这两堆果子合并成含有 \(x + y\) 个果子的一堆。此次操作消耗的体力值是原来两堆果子数目的平均值，也就是 \(\frac{x + y}{2}\)。

现在，乔治已经帮你把果子堆按照果子数目排好了顺序，希望你为他找到一种策略，使得把所有果子合并成一堆，并且消耗尽可能少的体力值。请输出这个最少的体力消耗值，保留一位小数。

输入格式

第一行输入一个整数 \(T\) 表示数据组数。

对于第一组数据，先输入一个整数 \(n\)，表示果子堆数。

接下来一行，\(n\) 个整数，表示数列 \(a_i\)（保证 \(\forall i < j, a_i \leq a_j\)）。

对于剩下的 \(T - 1\) 组数据，将通过对上一组数据的数列 \(\{a_i\}\) 略作修改生成，规则如下：

对于每组数据，先输入一个整数 \(m\)，表示要修改的操作数。

接下来 \(m\) 行，每行两个整数 \(u, v\)，表示把上一组数据中的第 \(u\) 个数 \(a_u\) 改为 \(v\)（数据保证任何时刻都有 \(\forall i < j, a_i \leq a_j\)）。

当 \(m\) 次修改完成后，你就得到了当前这组测试数据的数列 \(\{a_i\}\)，你需要对这组数据求解出问题的答案。

输出格式

共 \(T\) 行，每一行代表对应测试数据下，把 \(n\) 个果子堆合并成一堆所消耗的体力值，输出保留一位小数。

样例

输入：

1
2
3
4
5
6
2
5
1 1 1 1 1
2
4 4
4 2

输出：

1
2
6.0
9.5

数据范围

\(1 \leq u \leq n \leq 5 \times 10^5\)，\(\sum m \leq 10^5\)，\(1 \leq T \leq 20\)，\(1 \leq a_i, v \leq 10^9\)。

注意每组数据（无论是否经过修改而产生的）都保证 \(\forall i < j, a_i \leq a_j\)。

注意到本题的提交语言禁用了O2优化，因此请尽量使用线性做法，并尽量避免使用STL库

思路与题解

只需要考虑每次合并的最小即可，开两个数组，一个存数据，另一个存新的和，每一次取出两个数组头部能弹出的最小的值，再放入新数组中，这样新数组也一定是递增的，一直进行下去，只剩一堆的时候就是答案

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
#include <iostream>

using namespace std;

using ll = long long;

ll getSum(ll *a, int n) {
    ll b[n];
    int i = 0, j = 0, k = 0;
    ll sum = 0;
    for (int t = 0; t < n-1; ++t) {
        ll x;
        if (i < n && (j >=k || a[i] < b[j])) x = a[i++];
        else x = b[j++];
        ll y;
        if (i < n && (j >=k || a[i] < b[j])) y = a[i++];
        else y = b[j++];

        ll z = x + y;
        b[k++] = z;
        sum += z;
    }
    return sum;
}

void print(ll sum) {
    if (sum % 2 == 0) {
        cout << sum / 2 << '.' << 0 << endl;
    } else {
        cout << sum / 2<< '.' << 5 << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T;
    cin >> T;
    int n;
    cin >> n;
    ll a[n];
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    ll sum = getSum(a, n);
    print(sum);
    for (int i = 1; i < T; ++i) {
        int m;
        cin >> m;
        while (m--) {
            int idx;
            ll val;
            cin >> idx >> val;
            a[idx - 1] = val;
        }
        sum = getSum(a, n);
        print(sum);
    }


    return 0;
}

E.SA. 乒乓球比赛

题目描述

Y 老师举办了学校的乒乓球赛，为了兼顾赛程和公平，她决定采用瑞士轮赛制。

瑞士轮赛制如下：\(2 \times n\) 名编号为 \(1 \sim 2n\) 的选手共进行 \(r\) 轮比赛。每轮比赛开始前，以及所有比赛结束后，都会按照总分从高到低对选手进行一次排名。选手的总分为第一轮开始的初始分数加上已参加过的所有比赛的得分和。总分相同的，约定编号较小的选手排名靠前。

每轮比赛的对阵安排与该轮比赛开始的的排名有关：第 1 名和第 2 名、第 3 名和第 4 名、……、第 \(2k-1\) 名和第 \(2k\) 名、……、第 \(2n-1\) 名和第 \(2n\) 名，各进行一场比赛。每场比赛胜者得 1 分，负者得 0 分。也就是说除了首轮以外，其它轮比赛的安排均不能事先确定，而是要取决于选手在之前比赛中的表现。

现给定每个选手的初始分数及其实力值，试计算在 \(r\) 轮比赛过后，排名第 \(q\) 的选手编号是多少。我们假设选手的实力值两两不同，且每场比赛中实力值较高的总能获胜。

输入格式

输入的第一行是三个正整数 \(n, r, q\)，每两个数之间用一个空格隔开，表示有 \(2 \times n\) 名选手、\(r\) 轮比赛，以及我们关心的名次 \(q\)。

第二行是 \(2 \times n\) 个非负整数 \(s_1, s_2, \ldots, s_{2n}\)，每两个数之间用一个空格隔开，其中 \(s_i\) 表示编号为 \(i\) 的选手的初始分数。

第三行是 \(2 \times n\) 个正整数 \(w_1, w_2, \ldots, w_{2n}\)，每两个数之间用一个空格隔开，其中 \(w_i\) 表示编号为 \(i\) 的选手的实力值。

输出格式

输出一个整数，即 \(r\) 轮比赛结束后，排名第 \(q\) 的选手的编号。

样例

输入：

1
2
3
2 4 2
7 6 6 7
10 5 20 15

输出：

1
1

数据范围

\(1 \leq n \leq 10^5, 1 \leq r \leq 300, 1 \leq q \leq 2n, 0 \leq s_1, s_2, \ldots, s_{2n} \leq 10^8, 1 \leq w_1, w_2, \ldots, w_{2n} \leq 10^8\)。

思路与题解

本来一开始思路是直接模拟的，每次排序后复杂度 \(O(rnlogn)\) 卡常了…

那只能第一次排序了，每一次结束后得到了 winner 和 loser 组都是有序的，写一个简单的 merge 即可，这样就是 \(O(nlogn+rn)\)的复杂度了

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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct node {
    int idx;
    int score;
    int power;
};

int n, r, q;
vector<node> v;
vector<node> winner;
vector<node> loser;

bool cmp(node& a, node& b) {
    if (a.score != b.score) return a.score > b.score;
    else return a.idx < b.idx;
}

void merge() {
    int i = 0, j = 0, k = 0;
    while (i < n && j < n) {
        if (cmp(winner[i], loser[j])) {
            v[k++] = winner[i++];
        } else {
            v[k++] = loser[j++];
        }
    }
    while (i < n) v[k++] = winner[i++];
    while (j < n) v[k++] = loser[j++];
}

void round() {
    for (int i = 0; i < n; ++i) {
        if (v[2*i].power > v[2*i+1].power) {
            v[2*i].score += 1;
            winner[i] = v[2*i];
            loser[i] = v[2*i+1];
        } else {
            v[2*i+1].score += 1;
            winner[i] = v[2*i+1];
            loser[i] = v[2*i];
        }
    }
    merge();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> n >> r >> q;
    v.resize(2*n);
    winner.resize(n);
    loser.resize(n);


    for (int i = 0; i < 2*n; ++i) {
        cin >> v[i].score;
        v[i].idx = i+1;
    }
     for (int i = 0; i < 2*n; ++i) {
         cin >> v[i].power;
     }

    sort(v.begin(), v.end(), cmp);

    while (r--) round();


    cout << v[q-1].idx;

    return 0;
}

SB. XRJ的钢琴键

题目背景

XRJ，人称钢琴小王子，乃是1-213寝室四大成员之一。

题目描述

XRJ的魔法钢琴有 \(n\) 个钢琴键，每个钢琴键有一个音乐值 \(c_i\)，这些值可正可负可为0。 XRJ手很长，一次可以按下区间 \([L, R]\) 里面的所有钢琴键，区间 \([L, R]\) 的音乐值为区间内钢琴键的音乐值的总和。 他想知道，音乐值大于零的区间到底有多少个？

合法区间 \([L, R]\) 应当满足 \(1 \leq L \leq R \leq n\)

输入格式

一行，一个整数 \(n\) 接下来 \(n\) 行，每行一个整数 \(c_i\)，代表第 \(i\) 个钢琴键的音乐值。

输出格式

一行，一个整数，代表音乐值大于零的区间的个数。

样例 #1

样例输入 #1

1
2
3
4
5
4
10
-10
7
-5

样例输出 #1

1
5

提示

100%的数据，\(n \leq 5 \times 10^5\)，\(|c_i| \leq 10^7\)。

思路与题解

先求前缀和，得到前缀和数组 sum ，[L,R] 区间和为 sum[R]-sum[L-1] ，要大于0 即 sum[R]>sum[L-1] ，所以问题转化为求有多少对 (i,j) 满足 i<j 且 sum[i]<sum[j] ，即顺序对问题

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
#include <iostream>
#include <vector>

using namespace std;
using ll = long long;

int n;
vector<long long> sum;
vector<long long> v;


ll merge(l, mid, r){
    vector<long long> temp;
    int i = l, j = mid + 1;
    ll count = 0;
    while (i <= mid && j <= r) {
        if (sum[i] < sum[j]) {
            temp.push_back(sum[i++]);
        } else {
            temp.push_back(sum[j++]);
            count += r - j + 1; // 对应逆序对为 mid - i + 1
        }
    }
    while (i <= mid) {
        temp.push_back(sum[i++]);
    }

    while (j <= r) {
        temp.push_back(sum[j++]);
    }

    for (int p = 0; p < temp.size(); ++p) {
        sum[l + p] = temp[p];
    }
    return count;
}

ll mergeSort(int l, int r){
    if(l >= r) return 0;
    ll count = 0;
    int mid = l + (r - l) / 2;
    count += mergeSort(l, mid);
    count += mergeSort(mid + 1, r);
    count += merge(l, mid, r);
    return count;
}

int main(){
    int n;
    cin >> n;
    sum.resize(n+1);
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        sum[i] = sum[i-1] + x;
    }
    cout << mergeSort(0, n);
    return 0;
}

SC. 数字管理

题目背景

在数字化背景下，数字实在是太多了，我们要删除掉一些。

题目描述

有一个很长的数字序列，它由数字集 \(\{1, 2, 3, 4, 5, 6, 7, 8, 9\}\) 组成。

现在，我们要从这个数字序列中删除 \(a_1\) 个1，再删除 \(a_2\) 个2，……，删除 \(a_9\) 个9。

删除掉这些数字之后，剩下的数字序列按照原来的相对顺序合拢，可以看成一个整数。问这个整数最大是多少。（保证问题有解）

输入格式

第一行，字符串 \(S\)，表示数字序列。

第二行 9 个数字表示 \(a_1, a_2, \ldots, a_9\)。

输出格式

输出一行，删掉指定数量的数字之后剩下的序列最大是多少。

样例 #1

样例输入 #1

1
2
12345
1 0 0 1 1 0 0 0 0

样例输出 #1

1
234

样例 #2

样例输入 #2

1
2
112345
2 1 1 0 0 0 0 0 0

样例输出 #2

1
45

样例 #3

样例输入 #3

1
2
8898443445
0 0 0 2 0 0 1 0 0

样例输出 #3

1
8984435

提示

【数据范围】：

对30%的数据满足，\(|S| \leq 10\)

另有30%的数据满足，\(S\) 仅由数字 \(\{1, 2\}\) 组成

对100%的数据满足，\(|S| \leq 10 + 3 \times 10^5\)，\(S\) 由 \(\{1, 2, 3, 4, 5, 6, 7, 8, 9\}\) 组成，问题保证有解

思路与题解

其实是一个类似单调栈的题目，维护一个单调递减栈，从左到右遍历字符串，如果当前字符需要删除，则跳过，否则尝试将栈顶元素弹出（前提是栈顶元素比当前元素小且后面还剩余足够的该元素可以删除）

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
#include <iostream>
#include <vector>

using namespace std;

int c2i(char c) {
    return c - '0';
}

int main() {
    string s;
    cin >> s;
    vector<int> v(10,0);
    for (int i = 1; i <= 9; ++i) {
        cin >> v[i];
    }

    vector<int> cnt(10, 0);
    for (char c : s) cnt[c2i(c)]++;

    vector<int> need(10, 0);
    for (int d = 0; d < 10; ++d) need[d] = cnt[d] - v[d];

    string st;
    int n = s.size();
    st.reserve(n);

    for (char c : s) {
        int cur = c2i(c);
        cnt[cur]--;
        if (need[cur] == 0) continue;
        while (!st.empty()) {
            int top = c2i(st.back());
            if (top < cur && cnt[top] - 1 >= need[top]) {
                st.pop_back();
                need[top]++;
            } else break;
        }

        st.push_back(c);
        need[cur]--;
    }
    cout << st;
    return 0;
}
  • Title: 数据结构作业题解05
  • Author: exdoubled
  • Created at : 2025-10-23 17:00:00
  • Updated at : 2025-12-27 20:23:47
  • Link: https://github.com/exdoubled/exdoubled.github.io.git/sjjg/homework05/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
数据结构作业题解05
  1. A. 血魔训练 II
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
      1. 样例 1
      2. 样例 2
      3. 样例 3
    5. 数据范围
    6. 思路与题解
  2. B. 逆序对
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
      1. 样例 1
      2. 样例 2
    5. 数据范围
    6. 思路与题解
  3. C. 你美还是我美
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  4. D. 新·合并果子
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  5. E.SA. 乒乓球比赛
    1. 题目描述
    2. 输入格式
    3. 输出格式
    4. 样例
    5. 数据范围
    6. 思路与题解
  6. SB. XRJ的钢琴键
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 样例 #1
    6. 提示
    7. 思路与题解
  7. SC. 数字管理
    1. 题目背景
    2. 题目描述
    3. 输入格式
    4. 输出格式
    5. 样例 #1
    6. 样例 #2
    7. 样例 #3
    8. 提示
    9. 思路与题解