L: Swap Space
問題
n個のHDDがある。
それぞれは現在 容量a_iで、一つづつ取り替えて容量b_iにしたい。
HDDは全てフルに容量が埋まっており、取り替えるときはデータをn個の中の他のHDD、もしくは追加のHDDに移して、空になってからb_iになる。複数に分けて移しても良い。
最終的にデータを元のHDDに入れる必要はなく、追加のHDDに残しても良い。
追加のHDDは最小でいくらの容量が必要か。
制約
n <= 1,000,000
a, b <= 1,000,000,000
解法
超過容量を最初0として、任意の(a_i, b_i)を順番に適用させると、現在の超過容量cから c+a_iになり、c+a_i-b_iになる。
この超過容量の最大値が小さくなるように(a_i, b_i)の順番を求めたい。
a_i < b_i のものから処理するのが、超過容量が負の方向に伸びるので良い。
当然a_iが小さいものから処理するのが最適。
a_i >= b_i のものは b_iが大きいものから処理するのが最適。
あまり自明ではないが 超過容量の遷移を逆順に見ると、c', c'+b_i, c'+b_i-a_i のように移るので、逆順でb_i小さい順 = もとの順でb_i大きい順である。
コード
#include<cstdio> #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cstring> using namespace std; typedef long long LL; typedef vector<int> VI; #define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i) #define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i) #define eprintf(s...) fprintf(stderr, s) template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; } template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; } int N; LL A[1000111], B[1000111]; int main() { scanf("%d", &N); REP (i, N) scanf("%lld%lld", A+i, B+i); vector<pair<LL, LL> > inc, dec; REP (i, N) { if (A[i] < B[i]) inc.push_back(make_pair(A[i], B[i])); else dec.push_back(make_pair(B[i], A[i])); } sort(inc.begin(), inc.end()); LL ext = 0, ans = 0; EACH (e, inc) { if (e->first > ext) { ans += e->first - ext; ext = e->first; } ext += e->second - e->first; } sort(dec.rbegin(), dec.rend()); EACH (e, dec) { if (e->second > ext) { ans += e->second - ext; ext = e->second; } ext += e->first - e->second; } printf("%lld\n", ans); return 0; }