0w1

CFR 799 E. Aquarium decoration ( Binary Search )

Problem - E - Codeforces

題意:
有 N 個商品,用價格描述。你一共要選擇 M 樣物品,使得 Masha 喜歡其中至少 K 件,Arkady 也喜歡其中至少 K 件。問最小花費,無解輸出 -1。

制約:
The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤ m ≤ n, 1 ≤ k ≤ n) — the number of decorations, how many decorations the friends should choose, how many decorations each of them should like among the chosen.
The second line contains n integers c1, c2, ..., cn (1 ≤ ci ≤ 1e9) — decorations costs.
The third line contains single integer a (1 ≤ a ≤ n) — the number of decorations liked by Masha. The fourth line contains a distinct integers x1, x2, ..., xa (1 ≤ xi ≤ n) — the ids of decorations liked by Masha.
The next two lines describe decorations liked by Arkady in the same format.

解法:
將兩人都不喜歡的,只有 Arkady 喜歡的,只有 Masha 喜歡的,兩人都喜歡的,分為四個不同類,排序好,準備從最小價格開始取。
考慮枚舉 Masha 和 Arkady 都喜歡的物品納入的數量。這時候可以很快判斷這是不是有解的。若有解,那麼先透過適當地取兩個人分別喜歡的,保證兩個人都喜歡至少 K 件。接著要充填當前商品數量和 M 的差距。二分搜最佳充填方案用的商品最大值。未滿這個最大值的一定是全部都要取,取完之後再看還剩下多少要填充,乘上這個最大值再添上去就是答案。

時間 / 空間複雜度:
O( N lg N )

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

const int MAXN = int( 2e5 );

int N, M, K;
int C[ MAXN ];
int liked[ MAXN ];

vector< int > cost[ 3 + 1 ];
vector< long long > pcost[ 3 + 1 ];

signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N >> M >> K;
  for( int i = 0; i < N; ++i ) {
    cin >> C[ i ];
  }
  {
    int len;
    cin >> len;
    for( int i = 0; i < len; ++i ) {
      int v;
      cin >> v;
      liked[ v - 1 ] |= 1;
    }
    cin >> len;
    for( int i = 0; i < len; ++i ) {
      int v;
      cin >> v;
      liked[ v - 1 ] |= 2;
    }
  }
  for( int i = 0; i < N; ++i ) {
    cost[ liked[ i ] ].emplace_back( C[ i ] );
  }
  for( int i = 0; i <= 3; ++i ) {
    sort( cost[ i ].begin(), cost[ i ].end() );
    pcost[ i ].assign( cost[ i ].size() + 1, 0 );
    for( int j = 0; j < cost[ i ].size(); ++j ) {
      pcost[ i ][ j + 1 ] = pcost[ i ][ j ] + cost[ i ][ j ];
    }
  }
  long long ans = 1LL << 60;
  for( int t = 0; t <= cost[ 3 ].size(); ++t ) {
    if( t + min( cost[ 1 ].size(), cost[ 2 ].size() ) < K ) continue;
    if( t + cost[ 0 ].size() + cost[ 1 ].size() + cost[ 2 ].size() < M ) continue;
    int st = max( 0, K - t );
    if( t + st + st > M ) continue;
    int lb = 0, ub = int( 1e9 ); // lb not ok ub ok of max value taken
    while( lb + 1 != ub ) {
      int mid = lb + ub >> 1;
      int cnt = t;
      cnt += upper_bound( cost[ 0 ].begin(), cost[ 0 ].end(), mid ) - cost[ 0 ].begin();
      cnt += upper_bound( cost[ 1 ].begin() + st, cost[ 1 ].end(), mid ) - cost[ 1 ].begin();
      cnt += upper_bound( cost[ 2 ].begin() + st, cost[ 2 ].end(), mid ) - cost[ 2 ].begin();
      ( cnt >= M ? ub : lb ) = mid;
    }
    int cnt = t;
    long long tot = pcost[ 3 ][ t ];
    int f;
    f = upper_bound( cost[ 0 ].begin(), cost[ 0 ].end(), lb ) - cost[ 0 ].begin();
    cnt += f;
    tot += pcost[ 0 ][ f ];
    f = upper_bound( cost[ 1 ].begin() + st, cost[ 1 ].end(), lb ) - cost[ 1 ].begin();
    cnt += f;
    tot += pcost[ 1 ][ f ];
    f = upper_bound( cost[ 2 ].begin() + st, cost[ 2 ].end(), lb ) - cost[ 2 ].begin();
    cnt += f;
    tot += pcost[ 2 ][ f ];
    tot += 1LL * ( M - cnt ) * ub;
    ans = min( ans, tot );
  }
  if( ans == 1LL << 60 ) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
  return 0;
}