POJ 3045: Cow Acrobats

Greedy

http://poj.org/problem?id=3045

上からi-1番目まで決めているとする。i-1番目までの重さをWとすれば
i番目とi+1番目のriskは
W-S[i]
W+A[i]-S[i+1](Aは重さ)となる。ここでi番目とi+1番目のcowを入れ替えてみる

W-S[i+1]
W+A[i+1]-S[i]となる。
W-S[i]<=W+A[i+1]-S[i],W-S[i+1]<=W+A[i]-S[i+1]なので、結局
W+A[i]-S[i+1]とW+A[i+1]-S[i]の大小が重要であり、前者が小さくなるためには
A[i]+S[i]<=A[i+1]+S[i+1]であればよい。
よってA[i]+S[i]でsortして順番に使えばよい。

int A[MAX_N], B[MAX_N];
int C[MAX_N];

int N;

bool compare(int a, int b) {
	return A[a] + B[a] <= A[b] + B[b];
}


int main() {
	scanf("%d", &N);
	rep(i, 0, N) {
		scanf("%d%d", A + i, B + i);
		C[i] = i;
	}
	sort(C, C + N, compare);
	ll m = -(1LL << 60), sum = 0;
	rep(i, 0, N) {
		MAX(m, sum - B[C[i]]);
		sum += A[C[i]];
	}
	
	printf("%lld\n", m);
	return 0;
}

二分探索のsectionにある練習問題だけど二分探索出てこないぞ…
このA[i]+S[i]の条件を出すのに少しこんがらがった。xy平面使ったらわかりやすかったかも?