IOI 2016 Molecules ( Greedy )

http://ioinformatics.org/locations/ioi16/contest/day1/molecules/molecules-TWN.pdf
1956 - [IOI 2016] Molecules | TIOJ INFOR Online Judge

題意：
給 L, U, W, N, result，要你找一個在集合 S，使得該集合為下標的 W 的總和在 L 和 U 之間 ( 含 )，寫在 result 陣列裡。保證給的 W 裡的最大值和最小值的差不大於 U - L。

資料規模：
1 ≤ n ≤ 200000, 1 ≤ wi,u,l < 2^31

解法：
首先排序看看。
假設前 K 個元素比 U 大，那長度為 K 以上都沒有救。
假設後 K 個元素比 L 小，那長度為 K 以下都沒有救。
現在考慮前 K 個元素比 L 小，如果後 K 個元素也比 L 小，那麼 K 個元素無解。否則，一定存在解，而且會有至少一個連續區間是解。原因是，在往右爬行的過程中，因為會從比 L 小的狀態非遞減的增長，然後變到比 R 大的狀態，因此在途中一定會有轉變的那個過程。假設無解，那麼一定是某個時候將尾巴丟掉之後加入這個頭，突然從比 L 小的狀態變成了比 U 大的狀態。然而這是不可能的，因為題目保證了最大值和最小值得差不超過 U - L。

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

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

typedef long long ll;

int solve( int L, int U, int* W, int N, int* result ){
  vector< int > ord( N );
  for( int i = 0; i < N; ++i ){
    ord[ i ] = i;
  }
  sort( ord.begin(), ord.end(), [ & ]( int i, int j ){ return W[ i ] < W[ j ]; } );
  ll sum = 0;
  for( int lb = 0, rb = 0; lb < N; ++lb ){
    while( sum < L and rb < N ){
      sum += W[ ord[ rb++ ] ];
    }
    if( L <= sum and sum <= U ){
      for( int i = lb; i < rb; ++i ){
        result[ i - lb ] = ord[ i ];
      }
      return rb - lb;
    }
    if( lb < rb ) sum -= W[ ord[ lb ] ];
  }
  return 0;
}