题解：P7072 [CSP-J2020] 直播获奖

· · 题解

前言

这是一种黑科技解法，极为精简，不妨为想不到正解时的一种思路。

思路

容易想到的思路是，每次输入后都重新排序。但因为每次是在一个有序数列中加入一个新元素，实际上我们只要把这个新元素插入到这个数列中即可。
利用单次插入排序或冒泡排序，可以做到 O(n) 插入。

接下来，我们使用黑科技来优化插入过程。
C++ 的 STL 库中提供了容器 vector，利用这个容器的内置插入函数 insert 可以做到常数极小的 O(n) 插入元素到特定位置。
关于找到一个元素排在一个有序数列中的第几位，可以利用二分算法。利用 C++ 的 STL 库函数 lower_bound 可以实现二分查找。

时间复杂度为 O(n^2)，但根据个人经验，利用 insert 来维护有序的 vector 时间复杂度近似于 O(n\log^{2}n) 和 O(n\sqrt{n})。根据实际测试，即便不开 O2，不关同步流，此方法依然能以不过半的时间通过本题。

在普及组内，一般不会卡这个方法，我曾在一场洛谷入门赛中用这个方法秒切了最后一题。你甚至可以用这种方法通过洛谷的平衡树模板。

代码

#include<bits/stdc++.h>
using namespace std;
int n,w;
vector<int>a;
int main(){
    cin>>n>>w;
    for(int p=1;p<=n;p++){
        int x; cin>>x;
        a.insert(lower_bound(a.begin(),a.end(),x),x);
        cout<<a[min(p-1,p-(p*w)/100)]<<' ';
    }
    return 0;
}