POJ-3045 : Cow Acrobats

問題概要

長さN(<50000)の数列WとSがある。適当に並び替えて、max_{1<=i<=n} (sum_{i

解法

重さと力の和が大きいやつから順に並べれば良い。

acceptされたコード

計算量O(N*log N)。

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

const int MAX_N = (int)(5e4);
const int INF = (int)(1e9 + 10);

int N;
int ws[MAX_N], ss[MAX_N];
int xs[MAX_N], ids[MAX_N];

bool cmp(int i, int j){
	return xs[i] > xs[j];
}

void init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", ws+i, ss+i);
	}
}

int solve(){
	int total = 0;
	for(int i=0; i<N; i++){
		xs[i] = ss[i] + ws[i];
		total += ws[i];
		ids[i] = i;
	}

	sort(ids, ids+N, cmp);
	sort(xs, xs+N, greater<int>());

	int ans = -INF;
	for(int i=0; i<N; i++){
		const int idx = ids[i];
		total -= ws[idx];
		ans = max(ans, total - ss[idx]);
	}

	return ans;
}

int main(){
	init();
	printf("%d\n", solve());

	return 0;
}