ACM-ICPC World Finals 2016 L解法

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