[Codeforces 1082C]Multi-Subject Competition

[Codeforces 1082C]Multi-Subject Competition

문제 설명 : 

여러 명의 학생들이 대회에 참가하려고 한다. 대회에는 총 m가지의 종목이 있다. 입력으로 각 학생들이 할 수 있는 종목의 종류와, 그 종목에서의 능력치가 주어진다. 각 종목에 참가하는 학생의 수는 모두 동일해야한다고 할 때, 참가하는 학생들의 능력치의 합이 최대가 되도록 하는 문제이다.

풀이 : 

풀이가 엄청 간단한 문제인데 왜 이렇게 어렵게 생각했나 싶은 문제이다. 우선 2차원 벡터를 선언해서 각 종목별로 학생들의 능력치를 저장한 다음 각 종목 별로 능력치 순으로 내림차순 정렬을 한다. 그리고 sum[]이라는 배열에다가 현재 종목의 누적합이 0이상일 때만 더해준다. 이 과정이 끝나면 sum배열의 1~n번까지의 인덱스에는 각 종목에 i명의 학생이 출전 했을 때의 능력치들의 합이 저장되어 있다. 따라서 나는 sum[1]~sum[n]중에서 가장 큰 값이 정답이 된다.

주의할 점 : 

문제에서 입력으로 학생들의 능력치가 음수가 주어질 수 있으며, 능력치들의 최대 합이 음수라면 0을 출력해야 한다. 이 예외만 따로 처리해주도록 하자.

배운 점 : 

솔루션이 생각보다 매우 간단한 문제이다. 이런 문제는 특성상 다음에 비슷한 유형의 문제가 나왔을 때도 똑같이 아이디어를 떠올릴 수 있을 지가 불확실하다. 

코드 : 

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<iostream>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stdlib.h>
#include<stack>
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,int> Cord;
typedef long long ll;
/****************************Default Template******************************/
// #define SIZE
// #define IMP
// #define INF
// const int MOD=
struct S{
    int a,b;
 
    S(){}
    S(int _a,int _b){
        a=_a;
        b=_b;
    }
 
    const bool operator<(const S &o) const{
        return a<o.a;
    }
};
priority_queue<int> pq;
priority_queue<int,vector<int>,greater<int>> mpq;
map<int,int> mp;
stack<int> st;
set<int> set_i;
/****************************Default Template******************************/
const int SIZE= 100009;
 
 
vector<int> v[SIZE];
int sum[SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        int a,b;    scanf("%d %d",&a,&b);
        v[a].push_back(b);
    }
 
    for(int i=1 ; i<=m ; i++) 
        sort(v[i].begin(),v[i].end(),greater<int>());
 
    for(int i=1 ; i<=m ; i++){
        int cur=0;
        for(int j=0 ; j<v[i].size() ; j++){
            cur+=v[i][j];
            if(cur<0) break;
            sum[j+1]+=cur;
        }
    }
    int ans=0;
    for(int i=1 ; i<=n ; i++)
        ans=max(ans,sum[i]);
    printf("%d\n",ans);
 
    return 0;
}