Description
某个游戏在游戏者进行完一局之后，会给出这一局的分数。现在游戏制作者需要新增一个功能，使得它在给出分数
的同时，能够给出这局游戏的得分在游戏者之前进行的局的得分中排第几（简单的说，就是计算之前有多少局的分
数比这一局得分高，然后将这个值加一输出）。现在游戏公司找到了你，希望你能解决他们的难题。
Input
第一行一个整数nn表示游戏者总共进行过的局数。以下nn行每行一个整数，表示该局的得分。
Output
仅一个数，表示你的系统需要输出的nn个数的平均值。保留两位小数输出。
Sample Input
5
100
200
150
170
50
Sample Output
2.20
说明：
要输出的五个排名值分别是：11、11、22、22、55，平均值为2.202.20。
数据范围：
nn不超过100000100000，得分的值为非负整数，并且不超过109109。
HINT
思路
splay直接模拟题目要求。
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | #include <cstdio>const int maxn=100000;struct splay_tree{ int fa[maxn+10],son[2][maxn+10],val[maxn+10],size[maxn+10],cnt[maxn+10],root,tot; inline int t(int x) { return son[1][fa[x]]==x; } inline int updata(int x) { return size[x]=size[son[0][x]]+size[son[1][x]]+cnt[x]; } inline int rotate(int x) { int k=t(x),f=fa[x]; if(fa[f]) { son[t(f)][fa[f]]=x; } fa[x]=fa[f]; if(son[!k][x]) { fa[son[!k][x]]=f; } son[k][f]=son[!k][x]; fa[f]=x; son[!k][x]=f; updata(f); updata(x); return 0; } inline int splay(int x,int c) { while(fa[x]!=c) { int f=fa[x]; if(fa[f]==c) { rotate(x); } else if(t(x)==t(f)) { rotate(f); rotate(x); } else { rotate(x); rotate(x); } } if(!c) { root=x; } return 0; } inline int work(int x) { if(!root) { ++tot; root=tot; fa[tot]=son[0][tot]=son[1][tot]=0; size[tot]=cnt[tot]=1; val[tot]=x; return 1; } int now=root; while(now) { if(val[now]==x) { ++cnt[now]; splay(now,0); return size[son[1][now]]+1; } else { int k=(val[now]<x); if(!son[k][now]) { ++tot; son[k][now]=tot; val[tot]=x; cnt[tot]=1; fa[tot]=now; son[0][tot]=son[1][tot]=0; break; } now=son[k][now]; } } splay(tot,0); updata(tot); return size[son[1][tot]]+1; }};splay_tree st;int n,a;long long sum;double ans;int main(){ scanf("%d",&n); for(register int i=1; i<=n; ++i) { scanf("%d",&a); sum+=st.work(a); } ans=(1.0*sum)/n; printf("%.2lf\n",ans); return 0;} |
分享分享！！！！！！！
9.9 分
0 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复