ARC 073 E - Ball Coloring ( Greedy )

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder

題意：
有 N 個箱子，裡面有兩個球，球有各自的重量。對於每個箱子，都需要將其中一顆球放到袋子 A，另一顆放到袋子 B。一個袋子的價值是其中最大的重量和最小的重量的差。求最小的價值乘積。

制約：
1≦N≦200000
1≦xi,yi≦1e9

解法：
分開討論最小，最大值在哪裡。
若最小值在 A 袋，最大值在 B 袋：
__那麼對於任意的箱子，總是把重量小的球放到 A 袋一定比較好。
若最小值和最大值都在 A 袋：
__那麼等價於要求得一種取法使得 B 袋最大和最小的重量差最小。
__首先將所有箱子裡較小的球裝進 B 袋，接著運用單調性，依序把最小的球替換成另外一顆較大的球。顯然不會丟失最佳解。

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

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = int( 2e5 );
 
int N;
int X[ MAXN ], Y[ MAXN ];
 
signed main() {
  ios::sync_with_stdio( 0 );
  cin >> N;
  for( int i = 0; i < N; ++i ) {
    cin >> X[ i ] >> Y[ i ];
  }
  long long ans = 1LL * 1e18;
  int mine = min( *min_element( X, X + N ), *min_element( Y, Y + N ) );
  int maxe = max( *max_element( X, X + N ), *max_element( Y, Y + N ) );
  { // case 1
    int max_min = 0, min_max = int( 1e9 ) ;
    for( int i = 0; i < N; ++i ) {
      max_min = max( max_min, min( X[ i ], Y[ i ] ) );
      min_max = min( min_max, max( X[ i ], Y[ i ] ) );
    }
    ans = 1LL * ( max_min - mine ) * ( maxe - min_max );
  }
  { // case2
    priority_queue< pair< int, int > > pq;
    multiset< int > bag;
    for( int i = 0; i < N; ++i ) {
      pq.emplace( -min( X[ i ], Y[ i ] ), max( X[ i ], Y[ i ] ) );
      bag.emplace( min( X[ i ], Y[ i ] ) );
    }
    ans = min( ans, 1LL * ( maxe - mine ) * ( *--bag.end() - *bag.begin() ) );
    for( int i = 0; i < N; ++i ) {
      int s, t;
      tie( s, t ) = pq.top();
      pq.pop();
      bag.erase( bag.find( -s ) );
      bag.emplace( t );
      ans = min( ans, 1LL * ( maxe - mine ) * ( *--bag.end() - *bag.begin() ) );
    }
  }
  cout << ans << endl;
  return 0;
}