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; }