模拟+快排(50pts $n^2$)

• 每次获取一个成绩以后进行重新排序，然后获取对应名词的分数。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w;
    cin>>n>>w;
    vector<int> v;
    v.push_back(610);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
        int t=max(1,i*w/100); //计划录取人数
        sort(v.begin(),v.end(),greater<int>());
        cout<<v[t]<<" ";
    }
    return 0;
}

模拟+插入排序( $n^2$ 85pts)

• 每次获取一个分数就插入到已经有序的数组之中。

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,w;
    cin>>n>>w;
    vector<int> v;
    v.push_back(610);
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
        
        int t=max(1,i*w/100); //计划录取人数
        int j=v.size()-2;
        while(j>=0&&v[j]<=x) //插入排序
        {
            v[j+1]=v[j];
            j--;
        }
        v[j+1]=x;
        cout<<v[t]<<" ";
    }
    return 0;
}

模拟+桶排($600n$ 100pts)

• 每次来一个人从高到低统计分数段的总和，找到对应第一个大于等于计算人数的分数段.

#include<bits/stdc++.h>
using namespace std;
const int N=610;
int cnt[N];
int main()
{
    int n,w;
    cin>>n>>w;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        cnt[x]++;
        
        int t=max(1,i*w/100); //计划录取人数
        int c=0;
        for(int j=600;j>=0;j--) //从高到底统计分数段的的人数和
        {
            c+=cnt[j];
            if(c>=t)
            {
                cout<<j<<" ";
                break;
            }
        }
    }
    return 0;
}