关于P5076的一点小理解

Xianzi_ · 2024-08-26 17:10:23 · 题解

题目传送门

Part.-1(?). 闲话

看了一下很多大佬们的题解啊，都很多都用了 BST multiset 树堆 之类的高级玩意儿，但是我过于蒟蒻，因此看不懂那些题解。感谢老师和 ~~（陪我打CS1.6的）~~ 同学，我最终还是用了一种较为野鸡的方法

了这道题，就来分享一下自己的心得。

Part.0. 思路

看到这道题时，我就想到了用 vector [^1] 来进行代码的实现。题目中没有明说数组的取值范围 ^2 ，用 vector 实在再合适不过了。于是我搞出了这样一个东西：

vector <int> v, id;

其中 v 是初始数组， id 是我们在进行1~4操作过程中调动的数组。

接下来就一个个看各项操作吧。

Part.1. 主体

I.操作1 给数求排名

1.定义数 x 的排名为集合中小于 x 的数的个数 +1 。查询数 x 的排名。注意 x 不一定在集合里。

好的，我们要求 x 的排名，那干脆就加进原本的 id 数组好了（之后的步骤也会出现）。这里其实不用管去重的问题，把它 sort 一遍之后直接查询最前面一个就可以了。

代码实现也很简单：

int j;
id = v;
id.push_back(x);
sort(id.begin(), id.end());
for(j = 0; j < id.size(); j++){
    if (x == id[j]){
        cout << j + 1 << endl;
        break;
    }
}

第一个操作很简单就可以完成了。

II.操作2 给排名求数

2.查询排名为 x (x≥1) 的数。保证集合里至少有 x 个数。

基本思路和操作1差不多，但是实现更简单了。

id = v;
sort(id.begin(), id.end());
cout << id[x - 1] << endl;

到这里还是很简单吧？

III.操作3 给数求前驱

3.求 x 的前驱（前驱定义为小于 x，且最大的数）。若不存在则输出 −2147483647 。

这个时候，我们要考虑去重的问题了，不然会有些小bug（自己卡过好几次了， Subtest#1 都没过）。去重的话，我用了一个小巧可爱的 flag 来帮助我们。去重实现：

for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
if (!flag) id.push_back(x);

（这里我要解释一下，我在最开始写代码时把 flag 作为全局变量，所以截取的代码直接看会有点奇怪）

接下来就可以排序+查找了。

sort(id.begin(), id.end());
for (j = 0; j < id.size(); j++){
    if (x == id[j] && j != 0){
        flag = 1;
        cout << id[j - 1] << endl;
        break;
    }
}
if (!flag) cout << -2147483647 << endl;

还是比较美观的。

IV.操作4 给数求后继

4.求 x 的后继（后继定义为大于 x ，且最小的数）。若不存在则输出 2147483647 。

基本思路和操作3一样，但是注意小细节。去重同，排序同，查找要注意一下。代码实现：

for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
if (!flag) id.push_back(x);
flag = 0;
sort(id.begin(), id.end());
for (j = 0; j < id.size(); j++){
    if (x == id[j] && j != id.size() - 1){
        flag = 1;
        cout << id[j + 1] << endl;
        break;
    }
}
if (!flag) cout << 2147483647 << endl;

最难的操作3和4都这样水灵灵地搞完了。

V.操作5 给数入数组

5.插入一个数 x ，本题的数据保证插入前 x 不在集合中。

这不用思考了吧？

v.push_back(x);

Part.2. AC 代码

直接附上吧（饥渴难耐）

#include "bits/stdc++.h"
using namespace std;
vector <int> v, id;
int q;
bool flag;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> q;
    for (int i = 1; i <= q; i++){
        int op, x;
        cin >> op >> x;
        if (op == 1){
            int j;
            id = v;
            if (id.size() == 0){
                cout << 1 << endl;
                continue;
            }
            id.push_back(x);
            sort(id.begin(), id.end());
            for(j = 0; j < id.size(); j++){
                if (x == id[j]){
                    cout << j + 1 << endl;
                    break;
                }
            }   
        }
        if (op == 2){
            id = v;
            sort(id.begin(), id.end());
            cout << id[x - 1] << endl;
        }
        if (op == 3){
            int j;
            id = v;
            flag = 0;
            if (id.size() == 0){
                cout << -2147483647 << endl;
                continue;
            }
            for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
            if (!flag) id.push_back(x);
            flag = 0;
            sort(id.begin(), id.end());
            for (j = 0; j < id.size(); j++){
                if (x == id[j] && j != 0){
                    flag = 1;
                    cout << id[j - 1] << endl;
                    break;
                }
            }
            if (!flag) cout << -2147483647 << endl;
        }
        if (op == 4){
            int j;
            id = v;
            flag = 0;
            if (id.size() == 0){
                cout << 2147483647 << endl;
                continue;
            }
            for (int k = 0; k < id.size(); k++) if (x == id[k]) flag = 1;
            if (!flag) id.push_back(x);
            flag = 0;
            sort(id.begin(), id.end());
            for (j = 0; j < id.size(); j++){
                if (x == id[j] && j != id.size() - 1){
                    flag = 1;
                    cout << id[j + 1] << endl;
                    break;
                }
            }
            if (!flag) cout << 2147483647 << endl;
        }
        if (op == 5) v.push_back(x);
    }
    return 0;
}

如果你足够细心，你会发现我加了很多没必要的判空代码，就当防伪标记了吧（实际上是懒得改）

Part.3. 总结

怎么说呢，这道题是绿题还是有原因的，但整体上不难，也很容易一题多解，像是我这种蒟蒻都可以用一些独特的方法来 AC 这道题。

我的代码也可以进一步优化，像是前文说的flag、判空等等，也希望各位大佬指点。

最后，感谢你的阅读，谢谢！

（我要赶紧回去补BST了，再见）

\color{white}{我是彩蛋}

[^1]: vector 为STL容器中的可变长度数组。\ vector <typedef> typename (N, i); //建立一个元素类型为tpedef的可变长度数组typename，最开始有N个初始值为i的元素，N、i可省略。\ typename.push_back(a); //将元素 a 插入数组 typedef 的末尾并增加数组长度。\ typename.size(); //返回数组 typename 长度。\ typename.resize(n, m); //重新调整数组大小为n，新增元素初始化为m，m可省略。

操作次数q不超过 10e4 ，顶多只有10000个数据，用普通的数组也可以，但是 vector 类型有更多的优点，见下文\ 补充：普通数组在提交时容易 TLE