0w1

CFR 808 E. Selling Souvenirs ( Ad hoc, Monotonous )

Problem - 808E - Codeforces

題意:
有 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;
}