AOJ 2019 Princess's Marriage
問題
解法
距離と期待値を期待値の降順でソートしてどれだけ護衛を雇えるか計算する
心臓に悪いコード
int N, M; bool cmp(const pi &a, const pi &b){ return a.S > b.S; } int main(){ int D, P; while(scanf("%d%d", &N, &M) && N+M){ vector<pi>p(N); ll res = 0; rep(i, N){ scanf("%d%d", &D, &P); p[i] = make_pair(D, P); res += D*P; } sort(p.begin(), p.end(), cmp); rep(i, N){ if(p[i].F >= M){ res -= M * p[i].S; M = 0; }else{ res -= p[i].F * p[i].S; M -= p[i].F; } if(M == 0) break; } printf("%lld\n", res); } return 0; }