CFR 613 B. Skills ( Binary Search )

Problem - B - Codeforces

題意：
有 N 個技能，所有技能都用一個數值描述，上限皆為 A，你有 M 單位的金子，一個單位的金子可以提升一個技能的數值一個單位。你要最大化：數值為 A 的技能數量 * Cf + 最低的技能數值 * Cm。求最大化的值以及方案。

資料規模：
N ≤ 1e5
A ≤ 1e9
Cf, Cm ≤ 1000
M ≤ 1e15

解法：
一開始猜測是個凸函數，直接三分搜亂做了下去，結果頻頻 26 WA，貌似不是凸函數。。。
考慮枚舉其中一樣，因為最低的技能數值是連續的不好枚舉，所以決定枚舉升到上限的技能數量。每次枚舉時，二分搜出可行的最大最低技能數值，這部分用前綴合搞一下就可以了。但是特別要注意 46 行那裡，補好的就直接不在二分搜那裡包含了，因為肯定沒補好的事。這細節沒弄清楚的話會重複扣掉已經升到超過所沒舉的最低數值的貢獻。

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

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

template< class T1, class T2 >
bool upmax( T1 &x, T2 v ){
  if( x >= v ) return 0;
  x = v; return 1;
}

const int MAXN = ( int ) 1e5;

int N, A, Cf, Cm;
long long M;
int a[ MAXN ];
long long lpfx[ MAXN + 1 ];
long long gpfx[ MAXN + 1 ];
int lord[ MAXN ];
int gord[ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  {
    cin >> N >> A >> Cf >> Cm >> M;
    for( int i = 0; i < N; ++i ){
      cin >> a[ i ];
      gord[ i ] = i;
      lord[ i ] = i;
    }
    sort( lord, lord + N, [ & ]( int i, int j ){ return a[ i ] < a[ j ]; } );
    sort( gord, gord + N, [ & ]( int i, int j ){ return a[ i ] > a[ j ]; } );
    for( int i = 0; i < N; ++i ){
      lpfx[ i + 1 ] = lpfx[ i ] + a[ lord[ i ] ];
      gpfx[ i + 1 ] = gpfx[ i ] + a[ gord[ i ] ];
    }
  }
  {
    long long maxv = -1;
    int bestg, bestl, bestp;
    for( int i = 0; i <= N; ++i ){
      long long value = 1LL * i * Cf;
      long long cost = 1LL * i * A - gpfx[ i ];
      if( cost > M ) continue;
      int mins, minf; // maximum threshold of minimum, skills involved in this update
      for( int lb = 0, rb = A; lb <= rb; ){
        int mid = lb + rb >> 1;
        int f = N - i; // !!!!!!
        {
          for( int lb = 0, rb = N - i - 1; lb <= rb; ){
            int m = lb + rb >> 1;
            if( a[ lord[ m ] ] >= mid ){
              f = m;
              rb = m - 1;
            } else{
              lb = m + 1;
            }
          }
        }
        if( cost + 1LL * f * mid - lpfx[ f ] <= M ){
          mins = mid;
          minf = f;
          lb = mid + 1;
        } else{
          rb = mid - 1;
        }
      }
      if( upmax( maxv, value + 1LL * mins * Cm ) ){
        bestg = i;
        bestl = mins;
        bestp = minf;
      }
    }
    cout << maxv << endl;
    vector< int > ans( N );
    for( int i = 0; i < N; ++i ){
      ans[ i ] = a[ i ];
    }
    for( int i = 0; i < bestg; ++i ){
      ans[ gord[ i ] ] = A;
    }
    for( int i = 0; i < bestp; ++i ){
      ans[ lord[ i ] ] = bestl;
    }
    for( int i = 0; i < N; ++i ){
      cout << ans[ i ] << " \n"[ i + 1 == N ];
    }
  }
  return 0;
}