2016년 5월 10일 화요일

2865 - 나는 위대한 슈퍼스타K

https://www.acmicpc.net/problem/2865

본선에 $K$명만 나갈수 있다. 한 사람이 여러 장르를 부를 수는 없지만, 여러 사람이 같은 장르를 부를 수는 있다.

굵은 글씨가 문제의 핵심인 것 같다. 각 참가자의 제일 높은 점수를 더하면 된다.
$K$명만 선발해야하므로, 최고점수가 높은 순으로 $K$명을 고른다.


#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    vector<double> v[n]; // 각 사람의 점수들
    while(m--){
        for(int i=0; i<n; ++i){
            int man; double s;
            scanf("%d %lf ", &man, &s);
            v[man-1].push_back(s);
        }
    }
    priority_queue<double> pq;
    for(int i=0; i<n; ++i){
        sort(v[i].begin(), v[i].end());
        pq.push(v[i].back());
    }
    double ret = 0.;
    int count = 0;
    while(!pq.empty() && count++ < k){
        ret += pq.top();
        pq.pop();
    }
    printf("%.1lf", ret);
    return 0;
}
댓글 쓰기

게시글 목록