【AOJ 2019】Princess's Marriage
問題
Princess's Marriage | Aizu Online Judge
ソースコード
#include <iostream> #include <vector> #include <cstdlib> #include <cmath> #include <algorithm> #include <utility> using namespace std; #define rep(i,n) for(int i = 0 ; i < n ; i++) #define pii pair<int, int> #define pb push_back #define N 10000 bool comp(pii left, pii right){ if(left.second > right.second){ return true; }else{ return false; } } int main(){ int n, m; while(cin >> n >> m, n||m){ vector<pii> v(N); int d, p; rep(i, n){ cin >> d >> p; v.pb(pii(d, p)); } sort(v.begin(), v.end(), comp); rep(i, n){ if(v[i].first > m){ v[i].first -= m; break; }else{ m -= v[i].first; v[i].first = 0; } } int e=0; rep(i, v.size()){ e += (v[i].first * v[i].second); } cout << e << endl; } }
ソートして期待値の高いものから雇っていくようにすればよい。コードが汚い。