关于如何使用 vector 水过 P7072 这档事

· · 个人记录

先来了解 \text{vector} 的一个基本操作：

\text{vc.insert()}

其中有两个参数，第一个是指针即你要插入的位置，第二个是你要插入的数。

那你肯定要问，位置怎么找？没有关系，用二分查找，algorithm 自带的函数。

假如说我们要在 \text{vc} 中插入一个 \geq x 的数，我们可以这样写：

vector<int>::iterator ind = lower_bound(vc.begin(), vc.end(), x);

vc.insert(ind, x);

由于 \text{vector} 常数很小，\text{insert} 函数复杂度不高，我们可以通过这道题。

但是要注意：\text{vector} 默认升序排，而这道题要降序，我们只需减去 \text{size} 即可。

时间复杂度：{O(n \space log \space n)} 到 O(n \space\sqrt{n})

上代码：


#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

vector<int> arr;
vector<int>::iterator ps;

void Display(vector<int> vc) {
    for (int i = 0; i < vc.size(); i++) cout << vc[i] << " ";
    cout << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, w, curInt, ind;

    cin >> n >> w;

    for (int i = 1; i < n + 1; i++) {
        cin >> curInt;
        ps = lower_bound(arr.begin(), arr.end(), curInt);
        arr.insert(ps, curInt);
        //Display(arr);
        ind = max(1, i * w / 100);

        cout << arr[arr.size() - ind] << " ";
    }

    cout.flush();
    return 0;
}