티스토리 뷰

알고리즘 관련/BOJ

BOJ)3758 KCPC

JASON 자손9319 2017. 1. 15. 19:13

문제: icpc.me/3758


KCPC대회에서 각팀의 스코어가 주어졌을 때 정해진 기준에 따라 순위를 출력하는 문제이다.


제출 횟수나 최종 제출 시간은 쿼리를 받으면서 업데이트 시켜주면 되지만 최종 점수 같은 경우는 제출한 모든 기록중 문제당 최댓값이 업데이트 되므로 배열을 만들어 따로 저장해준 후에 업데이트 시켜준 뒤 조건에 맞게 정렬해주면 쉽게 구할 수 있는 문제이다.


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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int t, n, k, id, m, a, b, c;
int g[101][101];
struct student{
    int id,total, cnt, time;
} s[110];
bool cmp(student a, student b) {
    if (a.total == b.total) {
        if (a.cnt == b.cnt) 
            return a.time < b.time;
        return a.cnt < b.cnt;
    }
    return a.total > b.total;
}
int main() {
    scanf("%d"&t);
    while (t--) {
        int res;
        memset(s, 0sizeof(s));
        memset(g, 0sizeof(g));
        scanf("%d%d%d%d"&n, &k, &id, &m);
        for (int i = 0; i < n; i++)
            s[i].id = i + 1;
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d"&a, &b, &c);
            g[a][b] = max(g[a][b], c);
            s[a - 1].cnt++;
            s[a - 1].time = i;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++)
                s[i - 1].total += g[i][j];
        }
        sort(s, s + n, cmp);
        for (int i = 0; i < n; i++) {
            if (s[i].id == id)
                res = i + 1;
        }
        printf("%d\n", res);
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2910 빈도 정렬  (1) 2017.01.15
BOJ)7795 먹을 것인가 먹힐 것인가  (0) 2017.01.15
BOJ)3758 KCPC  (0) 2017.01.15
BOJ)8983 사냥꾼  (0) 2017.01.15
BOJ)10277 JuQueen  (0) 2017.01.15
BOJ)2877 4와 7  (0) 2017.01.15
TAG
댓글
댓글쓰기 폼