IOI 2007 Sails ( Greedy )

1343 - [IOI 2007, Day 1] Sails | TIOJ INFOR Online Judge

題意：
有 N 個桿子，第 i 個桿子的高度為 H[ i ]，待放的旗子數量為 K[ i ]。
對於一個高度，若有 x 個旗子，那麼該高度的貢獻為 x * ( x - 1 ) / 2。
求最小總貢獻。

資料規模：
輸入的第一行有一整數N (2 ≤ N ≤ 100 000)，代表這艘船上的船桅數。接下來的N行，每行都有兩個整數，H與K (1 ≤H ≤ 100 000, 1 ≤ K ≤ H)，分別代表每根船桅的高度與船帆數。船桅給定的順序是從船首到船尾。

解法：
先按照高度由小到大排序。
顯然每個高度旗子數量越接近越好，但越高的層放的機會一定越少。
可以發現，限制任意時刻旗子數量由低到高處一定是非遞增，不會丟失最佳解。
反證一下，如果有個高度一定要比下方的數量多才會最優，那麼將該高度一個旗子搬到下方旗子最少的高度，不會比較差，矛盾。
因此要維護的信息，事實上只需要高度，每個高度代表其以下都有一個旗子，因此用 BST 結構維護即可。
接著考慮一個新的桿子如何影響要維護的信息。
可以發現，最佳做法是選擇在當前的儲存的高度裡可以放的旗子數不超過當前桿子需要放的旗子數的最低高度，使之拉長到當前桿子高度，接著找選擇的高度以下的最高高度，由下到上補完還沒放的旗子。顯然補旗子一定不會補到第一次選擇的高度。

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

注意：
set 的 iterator ++ -- 什麼的刪除前刪除後要清楚，不然會很難除錯。。。

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

const int MAXN = ( int ) 1e5;

int N;
int H[ MAXN ], K[ MAXN ];
int ord[ MAXN ];

signed main(){
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ){
    cin >> H[ i ] >> K[ i ];
    ord[ i ] = i;
  }
  sort( ord, ord + N, [ & ]( int i, int j ){ return H[ i ] < H[ j ]; } );
  multiset< int > bag = { 0 };
  for( int i = 0; i < N; ++i ){
    int h = H[ ord[ i ] ], k = K[ ord[ i ] ];
    auto it = bag.lower_bound( h - k );
    auto it2 = it; --it2;
    if( it != bag.end() ){
      k -= h - *it;
      bag.emplace( h );
      if( *it ) bag.erase( it );
    }
    if( k ){
      // --it;
      bag.emplace( *it2 + k ); // bag.emplace( *it + k );
      if( *it2 ) bag.erase( it2 ); // if( *it ) bag.erase( it );
    }
  }
  int prev_hei = 0, lv = 0;
  long long ans = 0;
  for( auto it = bag.rbegin(); it != bag.rend(); ++it ){
    ans += 1LL * ( prev_hei - *it ) * lv * ( lv - 1 ) / 2;
    prev_hei = *it;
    ++lv;
  }
  cout << ans << endl;
  return 0;
}