CFR 799 E. Aquarium decoration ( Binary Search )
題意:
有 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; }