HNUST OJ 2211 Ranking

问题 H: Ranking
时间限制: 1 Sec  内存限制: 128 MB


题目描述

又到了百变联盟举行IQ测试比赛的时候了,这次的参赛者是来自玫瑰王国、白雪王国、黄金王国、白马王国、沙漠王国的众多好手。由于这次比赛参与人数众多,为了区分出选手的水平,主办方煞费苦心地准备了1000道题,每道题的分数是1000分,所以满分是1000000分(啊好难,我不参加了)。但是以前经常有选手爆零,出现尴尬的0分的场面,因此主办方决定报名参加比赛就是1分,即选手们的分数是1到1000000分(啊好“良心”)。 
因为参加人数众多,主办方为了对人才进行分类,把分数分成了1000个level,1到1000分属于level1,1001到2000分属于level2…最后999001到1000000分属于level1000。最令人意外的是,这次主办方请了聪明的GG Bond作为评委。 
但是历届比赛还没颁奖完,知道自己没获奖的人就走光了。今年为了防止出现这一尴尬场面和提高颁奖的紧张刺激性,因此GG Bond决定采取类似滚榜的形式。今年比赛只会根据交卷的先后顺序显示实时分数排名(当分数相同时排名一样)和其level_rank。 
即A在10:00交卷,那A只能知道在10:00交卷前的所有人中,他的实时分数排名和他的level_rank。而A想要知道最终的分数排名只能等待所有人交卷完。 
对于A的level_rank定义为:在A交卷前有多少个比A的分数level高的level出现过。 
例如: 有A,B,C,D四个人依次交卷,分数依次为5000,8000,5000,1000。A先交卷分数为5000属于level5,其分数排名为第1名并且level_rank为0。到B交卷分数为8000属于level8,其分数排名为第1名并且level_rank为0,因为前面没有大于level8的level出现过。到C交卷时分数为5000属于level5,而前面因为有level8出现过,因此其分数排名为第2名并且level_rank为1。而到D交卷时分数为1000属于level1,前面有level5和level8出现过,因此D的分数排名为4并且level_rank为2。 
GG Bond也同时负责了这一分数排名和level_rank的计算,但是他不会编程,你能帮他解决这个问题吗? 

输入

第一行包含一个数字n(n <= 10000), 表示参加比赛的人数。 
接下来n行,第i行表示第i个交卷的人的分数a[i](1<=a[i] <= 1000000)。  

输出

输出n行,第i行表示第i个交卷的人的level_rank和实时分数排名。 

样例输入
4
5000
8000
5000
1000

样例输出
0 1
0 1
1 2
2 4

思路

1. 题目很长,但别被题目吓到,还是很简单的

2. 一个分数的level可以用这个分数加999再除以1000来计算

3.实时排名就是看比这个分数高的有多少个,再加上1

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int a[10001],level[1001];
int main(){
    int N,score_rank,level_rank,max=0;
    scanf("%d",&N);
    for (int i = 0 ; i < N ; i++) {
        score_rank = 1 ;
        level_rank = 0 ;
        //输入成绩
        scanf("%d",&a[i]);
        //获取等级
        level[(a[i] + 999)/1000] = 1 ;
        //计算最大分数
        max = max >= a[i] ? max : a[i] ;
        //计算实时排名
        for (int j = 0 ; j <= i ; j++) {
            if (a[i] < a[j]) {
                score_rank++ ;
            }
        }
        //计算level_rank
        for (int j = (max + 999)/1000 ; j > (a[i] + 999)/1000 ; j--) {
                level_rank += level[j] ;
        }
        //输出
        printf("%d %d\n",level_rank,score_rank);
    }
    return 0;
}
 
/**************************************************************
    Problem: 2211
    User: 21XXXXXXXX
    Language: C++
    Result: 正确
    Time:279 ms
    Memory:2064 kb
****************************************************************/

上一篇:asp连接mdb数据库,并查询数据展示到web页面


下一篇:Generalized Mean Pooling