문제

문제 링크

문제 접근

  • 이 문제는 이분탐색을 알면 쉽게 풀 수 있는 문제이다.
  • k에 mid 값을 주어서 인용횟수가 k번 이상인 애들의 upper_bound를 구해준다.
  • 만일 k번 이상인 값들이 k개 이상 있다면 더 위를 확인해주고 없다면 아래쪽으로 이동한다.
  • 이 때 최대값을 확인하고 싶기 때문에 올라갈 때 ans를 계속 업데이트 하도록 한다.

코드

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int ans, n; 
int main(){
    scanf("%d", &n);
    vector<int> arr(n);
    for(int i = 0 ; i < n; i++)scanf("%d", &arr[i]);
    sort(arr.begin(), arr.end());
    int l = 0, r = arr[n-1];
    while(l <= r){
        int k = ( l + r ) / 2;
        int up = n - (lower_bound(arr.begin(), arr.end(), k) - arr.begin());
        if(up < k) r = k - 1;
        //k보다 같거나 많으면 끝까지 가서 제일 큰 애를 발견해내야해
        else ans = k, l = k + 1;
    }
    printf("%d", ans);
}

느낀점

  • 이분 탐색을 알기에 풀 수 있었다.
  • 풀 수 있었음에 감사하다!