CFR 389 E. Fox and Card Game ( Greedy, Game )

Problem - E - Codeforces

題意：
有 N 個堆，第 i 個堆有 S[ i ] 個元素，每個元素都有權值 C[ i ][ j ] 。玩家 A 每次選一個堆，取最上面的元素，玩家 B 每次選一個堆，取最下面的元素。玩家 A 開始，並輪流操作。求雙方最大化自己的權值總和為前提，玩家 A 和 B 會有的最終分數。

資料規模：
N ≤ 100
S[ i ] ≤ 100
C[ i ][ j ] ≤ 1000

解法：
考慮只有一個堆時，顯然 A 會拿上半 ( 向上取整 )，B 會拿下半。
考慮有兩個堆時，並以兩個堆的大小都為偶數為前提，若對 A 來說拿第一個堆的超過一半對 A 較有利，那會等價於 B 不拿第一個堆的一半以上則 B 會吃虧。顯然這個敘述裡的 A, B 交換依然成立。因此雙方都拿一半一定不會比較差 ( 也就是最佳策略 )。有了這個結論，就知道推廣到有任意多堆的情況也都會成立。
接著考慮有一些堆是奇數大小的情況，如果這樣的堆只存在一個，顯然 A 拿到。如果有兩個，A 將拿到比較大的那個，B 將拿到比較小的那個。如果有三個，A 將會拿到最大和第三大的，B 會拿到次大的。因此，將奇數大小的堆的中間元素取出來，第 2n + 1 大的給 A 加分，第 2n 大的給 B 加分即可。

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

const int MAXN = 100;

int N;
int S[ MAXN ];
vector< int > C[ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  vector< int > mid;
  int fp = 0, sp = 0;
  for( int i = 0; i < N; ++i ){
    cin >> S[ i ];
    C[ i ] = vector< int >( S[ i ] );
    for( int j = 0; j < S[ i ]; ++j ){
      cin >> C[ i ][ j ];
      if( j < S[ i ] / 2 ){
        fp += C[ i ][ j ];
      } else if( S[ i ] + 1 >> 1 <= j ){
        sp += C[ i ][ j ];
      }
    }
    if( S[ i ] & 1 ){
      mid.emplace_back( C[ i ][ S[ i ] / 2 ] );
    }
  }
  sort( mid.begin(), mid.end(), greater< int >() );
  for( int i = 0; i < mid.size(); i += 2 ){
    fp += mid[ i ];
    if( i + 1 < mid.size() ) sp += mid[ i + 1 ];
  }
  cout << fp << " " << sp << endl;
  return 0;
}