H - カンカンマート / Can Can Mart ～三分探索解法～

• Quiz
  • https://atcoder.jp/contests/past202104-open/tasks/past202104_h
• AC
  • https://atcoder.jp/contests/past202104-open/submissions/22367788
• 解説
  • editorialとは別の解法なので書いておく
  • 買う缶切りの数をx軸としたコスト関数を考えると凸になっているので三分探索が可能

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    // input
    ll N,M,K,Q;
    cin>>N>>M>>K>>Q;
    
    VI A,B;
    rep(i,N){
      ll p,t;cin>>p>>t;
      if(t==0){
        A.push_back(p);
      }else{
        B.push_back(p);
      }
    }
    SORT(A);
    SORT(B);
 
    ll left=0;
    ll right=ceil_div(SZ(B), K);
 
    // n個缶切りがある時のコスト
    auto f = [&](ll n){
      // 選べる個数
      if(SZ(A)+n*K<M)return inf;
      ll cost = Q*n;
      // 商品
      VI C = A;
      ll mi=min((ll)SZ(B), n*K);
      rep(i,mi)C.push_back(B[i]);
      SORT(C);
      rep(i,M)cost+=C[i];
      return cost;
    };
 
    while(right-left>2){
      ll p0 = (2 * left + 1 * right) / 3;
      ll p1 = (1 * left + 2 * right) / 3;
      
      ll d0 = f(p0);
      ll d1 = f(p1);
 
      if(d0<d1){
          right = p1;
      }else{
          left = p0;
      }
    }
    ll mi=inf;
    FOR(i,left,right+1){
      chmin(mi, f(i));
    }
    p(mi);
    
    return 0;
}