CFR 808 E. Selling Souvenirs ( Ad hoc, Monotonous )
題意:
有 N 個物品,你的背包容量為 M。第 i 個物品容量為 W[ i ],價值為 C[ i ]。求可容的最大可能價值總和。
制約:
1 ≤ N ≤ 1e5
1 ≤ M ≤ 3e5
1 ≤ W[ i ] ≤ 3
1 ≤ C[ i ] ≤ 1e9
解法:
如果只有兩種重量,那有多簡單。
考慮討論取的 W[ i ] = 1 的數量的奇偶性:
奇:選取價值最大的 W[ i ] = 1,接著從剩下的價值最大的 W[ i ] = 1 兩兩一對形成 W[ i ] = 2
偶:直接從價值最大的 W[ i ] = 1 兩兩一對形成 W[ i ] = 2
接著用單調性解決就可以了。
複雜度:
O( N lg N )
#include <bits/stdc++.h> using namespace std; const int MAXN = int( 1e5 ); const int MAXM = int( 3e5 ); int N, M; int W[ MAXN ], C[ MAXN ]; vector< int > vec[ 3 + 1 ]; signed main() { ios::sync_with_stdio( 0 ); cin >> N >> M; for( int i = 0; i < N; ++i ) { cin >> W[ i ] >> C[ i ]; vec[ W[ i ] ].emplace_back( C[ i ] ); } for( int i = 1; i <= 3; ++i ) { sort( vec[ i ].begin(), vec[ i ].end(), greater< int >() ); } long long ans = 0; if( not vec[ 1 ].empty() ) { // suppose optimal strategy takes odd number of elements from vec[ 1 ] long long sum = vec[ 1 ][ 0 ]; vector< int > f = vec[ 2 ]; for( int i = 1; i + 2 <= vec[ 1 ].size(); i += 2 ) { f.emplace_back( vec[ 1 ][ i ] + vec[ 1 ][ i + 1 ] ); } sort( f.begin(), f.end(), greater< int >() ); int ptr = 0; long long wei = M - 1; while( ptr < f.size() and wei >= 2 ) { wei -= 2; sum += f[ ptr++ ]; } ans = max( ans, sum ); for( int i = 0; i < vec[ 3 ].size(); ++i ) { wei -= 3; sum += vec[ 3 ][ i ]; while( 0 < ptr and wei < 0 ) { wei += 2; sum -= f[ --ptr ]; } if( wei < 0 ) break; ans = max( ans, sum ); } } { // suppose optimal strategy takes even number of elements from vec[ 1 ] long long sum = 0; vector< int > f = vec[ 2 ]; for( int i = 0; i + 2 <= vec[ 1 ].size(); i += 2 ) { f.emplace_back( vec[ 1 ][ i ] + vec[ 1 ][ i + 1 ] ); } sort( f.begin(), f.end(), greater< int >() ); int ptr = 0; long long wei = M; while( ptr < f.size() and wei >= 2 ) { wei -= 2; sum += f[ ptr++ ]; } ans = max( ans, sum ); for( int i = 0; i < vec[ 3 ].size(); ++i ) { wei -= 3; sum += vec[ 3 ][ i ]; while( 0 < ptr and wei < 0 ) { wei += 2; sum -= f[ --ptr ]; } if( wei < 0 ) break; ans = max( ans, sum ); } } cout << ans << endl; return 0; }