U E D R , A S I H C RSS

1R/2016_07_05 (rev. 1.3)

1R/2016_07_05


2. 참가자

이름 학번
박인서 15학번

3. 코드

3.1. 박인서

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	setbuf(stdout, NULL);
	
	int TC;
	int test_case;
    
	scanf("%d", &TC);
	for(test_case = 1; test_case <= TC; test_case++) {
	    int n;
	    vector<int> a;
	    scanf("%d", &n);
	    for(int i=0;i<n;i++){
	        int t;
	        scanf("%d", &t);
	        a.push_back(t);
	    }
	    sort(a.begin(),a.end());
	    
	    //마지막 대회 시행 및 1등 점수 저장
	    int max=0;
	    for(int i=0;i<n;i++)
	        if(max<a[i]+n-i) max=a[i]+n-i;
	    
	    //1등 가능성 따짐
	    int cnt=0;
	    for(int i=0;i<n;i++)
	        if(max<=a[i]+n) cnt++;

	    printf("Case #%d\n%d\n", test_case, cnt);
	}
	return 0;
}

4. 아이디어

4.1. 박인서

  • 마지막 대회에서 종합 점수 1등이 1점, 2등이 2점, ... , n등이 n점일 때 1등 가능성이 가장 많아짐.
  • 따라서 마지막 대회가 위와 같이 이상적으로 이루어진다고 가정하고, 마지막 대회 결과 최댓값을 각자가 1등 하였을 때를 비교한다.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:22:06
Processing time 0.0184 sec