[BOJ 15732] 도토리 숨기기

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

15732번: 도토리 숨기기

Tag : binary search

 

문제 요약

"\([l,r]\)에서 x간격으로 도토리를 하나씩 배치한다." 라는 규칙이 \(K\)개 존재한다.

이 때 \(D\)번째 도토리가 위치한 상자를 찾는 문제다.

 

풀이

1~i까지 상자의 도토리 개수 합이 단조증가하기 때문에 이분탐색을 사용할 수 있다.

1~i까지의 도토리 개수가 D개 미만인 최대 i를 구해 이 다음 것을 출력하면된다.

 

시간복잡도 : \(O(KlogN)\)

 

전체 코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}

ll N,K,D;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    cin>>N>>K>>D;
    vector<tuple<ll,ll,ll>>v(K);
    for(auto&[l,r,x]:v)cin>>l>>r>>x;
    auto chk=[&](ll m)->int{
        ll ret=0;
        for(auto&[l,r,x]:v){
            ret+=max(0ll,(min(m,r)-l+x))/x;
        }
//        cout<<m<<' '<<ret<<endl;
        return ret<D;
    };
    ll lo=0,hi=N+1;
    while(lo+1<hi){
        ll m=(lo+hi)/2;
        if(chk(m))lo=m;
        else hi=m;
    }
    cout<<hi<<endl;
}