[BOJ 21819] Acowdemia

- 문제 요약

 

소 베시는 컴퓨터 과학에 대한 그녀의 사랑과 언젠가 "베시 박사"가 되는 매력에 이끌려 컴퓨터 과학 박사 과정에 등록했습니다. 한동안 학술 연구에 종사한 그녀는 현재 N개의 논문(1<=N<=10^5)을 발표했으며, 그녀의 i번째 논문은 연구 문헌의 다른 논문에서 인용문(0<=ci<=10^5)을 축적했습니다.

Bessie는 한 학자의 성공은 그들의 h-지수에 의해 측정될 수 있다고 들었습니다. h-지수는 연구자가 적어도 h개의 논문을 가지고 있을 정도로 가장 큰 h개의 논문입니다. 예를 들어, 4개의 논문과 각 인용 횟수(1,100,2,3)가 있는 연구자의 h-지수는 2인 반면 인용 횟수가 (1,100,3,3)인 경우 h-지수는 3입니다.

Bessie는 h-지수를 높이기 위해 K개의 설문 조사 기사(0<=K<=10^5)까지 작성할 계획이며, 각각 과거 논문을 많이 인용합니다. 그러나 페이지 제한 때문에 그녀는 각 설문 조사에서 대부분의 L 논문만 인용할 수 있습니다(0<=L<=10^5). 물론 단일 설문조사에서 논문을 여러 번 인용할 수는 없습니다(그러나 여러 설문조사에서 논문을 인용할 수는 있습니다).

베시가 이 설문 조사 기사를 작성한 후에 얻을 수 있는 최대 h-index를 결정할 수 있도록 도와줍니다. Bessie는 그녀의 설문 조사 중 하나에서 설문 조사를 인용하는 것이 허용되지 않습니다.

베시의 연구 고문은 아마도 어느 시점에서 단지 자신의 지수를 높이기 위해 설문조사를 작성하는 것은 윤리적으로 의심스럽다는 것을 그녀에게 알려야 할 것입니다. 여기서 다른 학자들은 베시의 예를 따르는 것이 권장되지 않습니다.

 

 

- 알고리즘 정리

 

그냥 이분 탐색으로 그리디 하게 해결해 주면 됩니다.

(풀 때 자료형에 유의하세요...! ^^ 맞왜틀 3번 했습니다)

 

 

- 코드 작성

 

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

#define MAX 100001
typedef long long ll;
ll n,k,l,arr[MAX],lower,upper;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>l;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
	sort(arr,arr+n,greater<int>());
	lower=0,upper=n;
	while(lower<upper){
		int mid=(lower+upper+1)/2;
		ll w=0;
        for(int i=0;i<mid;i++){
        	w+=max(0LL,mid-arr[i]);
		}
		if(w<=k*l&&arr[mid-1]+k>=mid){
			lower=mid;
		}
        else{
        	upper=mid-1;
		}
	}
	cout<<upper;
}

코드 제출 결과