[BOJ] 21820 Acowdemia I

 

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

문제의 조건에 따라 잘 프로그래밍 해주면 되는 문제

 

지문 중

"... and of course she can cite each of her papers at most once."

( 그녀는 자신의 논문을 최대 한 번만 인용할 수 있습니다. )

라고 명시되어 있으므로

h-index 값 계산 시 주의해야 합니다

 

활용 알고리즘 : 이분 탐색 (매개 변수 탐색)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mx = (1e5)+5;

void solve(){

    ll n, l; cin >> n >> l;

    vector<ll> sums(mx, 0);

    vector<ll> cnts(mx, 0);

    for(int i=0; i<n; i++){

        int c; cin >> c;

        cnts[c]++;

    }

    sums[0] = cnts[0];

    for(int i=1; i<mx; i++) sums[i] = sums[i-1]+cnts[i];

    ll lo=0, hi=n;

    ll ans=0;

    while(lo <= hi){

        ll mid = (lo+hi)/2;

        if((n-sums[mid]+min(cnts[mid], l)) >= (mid+1)){

            ans = mid+1;

            lo = mid+1;

        } else hi = mid-1;

    }

    cout << ans;

}

int main(void){

    ios::sync_with_stdio(0);

    cin.tie(0);

    solve();

    return 0;

}

---

https://www.acmicpc.net/board/view/150762

1 1
0

[ans] 1

 

추가적으로 이상과 같은 반례를 주의해야 합니다