问题 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
****************************************************************/