CSP-J2020 洛谷P7072 直播获奖（Splay/桶排序）

题目描述

NOI2130 即将举行。为了增加观赏性，CCF 决定逐一评出每个选手的成绩，并直播即时的获奖分数线。本次竞赛的获奖率为 w%，即当前排名前 w% 的选手的最低成绩就是即时的分数线。

更具体地，若当前已评出了 p 个选手的成绩，则当前计划获奖人数为max(1,⌊p∗w%⌋)。如有选手成绩相同，则所有成绩并列的选手都能获奖，因此实际获奖人数可能比计划中多。

作为评测组的技术人员，请你帮 CCF 写一个直播程序。

输入格式

第一行有两个整数 n,w。分别代表选手总数与获奖率。
第二行有 n 个整数，依次代表逐一评出的选手成绩。

输出格式

只有一行，包含 n 个非负整数，依次代表选手成绩逐一评出后，即时的获奖分数线。相邻两个整数间用一个空格分隔。

看到这道题，第一反应是用Splay，因为这道题支持两个操作：插入元素和查询第k大元素，套模板就行了。

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 const int N=1e5+5;

 4 int n,w;

 5 int fa[N],lc[N],rc[N],vi[N],sze[N];

 6 int rt,T;

 7 bool Wrt(int x){

 8     return rc[fa[x]]==x;

 9 }

10

11 void pushup(int x){//更新子树大小

12     sze[x]=sze[lc[x]]+sze[rc[x]]+1;

13 }

14

15 void rot(int x){

16     int y=fa[x],z=fa[y];

17     int b=(lc[y]==x)?rc[x]:lc[x];

18     fa[x]=z,fa[y]=x;

19     if(b) fa[b]=y;

20     if(z) (y==lc[z]?lc[z]:rc[z])=x;

21     if(x==lc[y]) rc[x]=y,lc[y]=b;

22     else lc[x]=y,rc[y]=b;

23     pushup(y);pushup(x);

24 }

25

26 void Splay(int x,int tar){

27     while(fa[x]!=tar){

28         if(fa[fa[x]]!=tar)

29             Wrt(x)==Wrt(fa[x])?rot(fa[x]):rot(x);

30         rot(x);

31     }

32     if(!tar) rt=x;

33 }

34

35 void ins(int v){//插入元素

36     int x=rt,y=0,dir;

37     while(x){

38         ++sze[y=x];

39         if(v<=vi[x]) dir=0,x=lc[x];

40         else dir=1,x=rc[x];

41     }

42     fa[x=++T]=y,vi[x]=v,sze[x]=1;

43     if(y) (dir==0?lc[y]:rc[y])=x;

44     Splay(x,0);

45 }

46

47 int query(int x,int k){//查找第k个数

48     while(1){

49         int s=lc[x]?sze[lc[x]]+1:1;

50         if(k==s) return vi[x];

51         if(k>s) k-=s,x=rc[x];

52         else x=lc[x];

53     }

54 }

55

56 int main(){

57     scanf("%d%d",&n,&w);

58     for(int i=1;i<=n;i++){

59         int x;

60         scanf("%d",&x);

61         int k=max(1,i*w/100);

62         ins(x);

63         cout<<query(rt,i-k+1)<<" ";

64     }

65     return 0;

66 }

当然，本题还有更简单的方法，代码量也更小。

就是用桶排序，因为分数的范围非常小，只有600；（桶的下标就是元素的值）

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int t[N],n,w;

int main(){

    scanf("%d%d",&n,&w);

    for(int i=1;i<=n;i++){

        int x,sum=0;

        scanf("%d",&x);t[x]++;

        for(int j=600;j>=0;j--){

            sum+=t[j];

            if(sum>=max(1,i*w/100)){

                cout<<j<<" ";

                break;

            }

        }

    }

    return 0;

}

之前好像没太多接触过桶，今天又学到了，像这种题目值域比较小的，可以考虑用桶。

巴特西

CSP-J2020 洛谷P7072 直播获奖（Splay/桶排序）

题目描述

输入格式

输出格式

最新文章

热门文章