NEC Programming Contest 2021(AtCoder Beginner Contest 229) C - Cheese

NEC Programming Contest 2021(AtCoder Beginner Contest 229) C - Cheese

题目链接：C - Cheese (atcoder.jp)

Problem Statement

Takahashi, who works for a pizza restaurant, is making a delicious cheese pizza for staff meals.
There are N kinds of cheese in front of him.
The deliciousness of the i-th kind of cheese is Ai​ per gram, and Bi​ grams of this cheese are available.
The deliciousness of the pizza will be the total deliciousness of cheese he puts on top of the pizza.
However, using too much cheese would make his boss angry, so the pizza can have at most W grams of cheese on top of it.
Under this condition, find the maximum possible deliciousness of the pizza.

Constraints

• All values in input are integers.
• 1≤N≤3×105
• 1≤W≤3×108
• 1≤Ai​≤109
• 1≤Bi​≤1000

---

Input

Input is given from Standard Input in the following format:

N W
A1​ B1​
A2​ B2​
...
AN​ BN​

Output

Print the answer as an integer.

---

Sample Input 1 

3 5
3 1
4 2
2 3

Sample Output 1 

15

The optimal choice is to use 1 gram of cheese of the first kind, 2 grams of the second kind, and 2 grams of the third kind.
The pizza will have a deliciousness of 15.

---

Sample Input 2 

4 100
6 2
1 5
3 9
8 7

Sample Output 2 

100

There may be less than W grams of cheese in total.

---

Sample Input 3 Copy

Copy

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Sample Output 3 

2357689932073

题意：有n种奶酪，总质量不能超过w，

第i种美味值ai每g，有big

问总美味值最大是多少

思路：排序一下，美味值从大到小排序，然后遍历一遍，进行计算

#include
using namespace std;

struct node{
	long long a;
	long long b;
}arr[300005];

bool cmp(node a, node b){
	return a.a > b.a;
}

int main(){
	int n;
	long long w;
	cin >> n >> w;
	for(int i = 0; i < n; i++){
		cin >> arr[i].a >> arr[i].b;
	}

	sort(arr, arr + n, cmp);
	long long sum = 0;
	for(int i = 0; i < n; i++){
		sum += (arr[i].a * min(w, arr[i].b));
		w -= min(w, arr[i].b);
		if(w == 0){
			break;
		}
	}
	cout << sum << endl;
	return 0;
}