Posted on 2009-03-17 16:02
superman 閱讀(111)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 class Milk
6 {
7 public:
8 int price;
9 int amount;
10
11 bool operator < (const Milk & m) const
12 {
13 return price < m.price;
14 }
15 } milk[5000];
16
17 int main()
18 {
19 freopen("milk.in", "r", stdin);
20 freopen("milk.out", "w", stdout);
21
22 int n, m, ans = 0;
23
24 cin >> n >> m;
25 for (int i = 0; i < m; i++)
26 cin >> milk[i].price >> milk[i].amount;
27
28 sort(milk, milk + m);
29
30 int i = 0;
31 while (n)
32 {
33 ans += min(milk[i].amount, n) * milk[i].price;
34 n -= min(milk[i].amount, n);
35 i += 1;
36 }
37
38 cout << ans << endl;
39
40 return 0;
41 }
42