Algoogle

Algorithm for Programming Contest

JOI 春合宿 2007 Score

Category: JOI Tag: implementation

Score

問題概要


得点のリストが与えられるので, それぞれの順位を答えよ

解法


値に対してidを持ってソート.
ソートした値を順にみてi番目の順位は前の順位から変動したらi位, そうでなければ前と同じ.
これを各人に対して保存したらそれぞれの人を順に見ていく.

コード


(Score.cpp) download
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
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;

int n, r[100010];
pii x[100010];

void solve()
{
        sort(x,x+n);
        reverse(x,x+n);
        int rnk = 0, pv = -1;
        for (int i = 0; i < n; i++) {
                if(pv != x[i].first) rnk = i+1;
                pv = x[i].first;
                r[x[i].second] = rnk;
        }
        for (int i = 0; i < n; i++)
                cout << r[i] << endl;
}

void input()
{
        cin >> n;
        for (int i = 0; i < n; i++) {
                cin >> x[i].first;
                x[i].second = i;
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        solve();
        return 0;
}

Comments