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