洛谷 P2983 [USACO10FEB]Chocolate Buying S

这题其实不难但时间复杂度是大难点

题目描述

Bessie and the herd love chocolate so Farmer John is buying them some.

The Bovine Chocolate Store features N (1 <= N <= 100,000) kinds of chocolate in essentially unlimited quantities. Each type i of chocolate has price P_i (1 <= P_i <= 10^18) per piece and there are C_i (1 <= C_i <= 10^18) cows that want that type of chocolate.

Farmer John has a budget of B (1 <= B <= 10^18) that he can spend on chocolates for the cows. What is the maximum number of cows that he can satisfy? All cows only want one type of chocolate, and will be satisfied only by that type.

Consider an example where FJ has 50 to spend on 5 different types of chocolate. A total of eleven cows have various chocolate preferences:

Chocolate_Type Per_Chocolate_Cost Cows_preferring_this_type 1 5 3

2 1 1

3 10 4

4 7 2

5 60 1

Obviously, FJ can't purchase chocolate type 5, since he doesn't have enough money. Even if it cost only 50, it's a counterproductive purchase since only one cow would be satisfied.

Looking at the chocolates start at the less expensive ones, he can * purchase 1 chocolate of type #2 for 1 x 1 leaving 50- 1=49, then * purchase 3 chocolate of type #1 for 3 x 5 leaving 49-15=34, then * purchase 2 chocolate of type #4 for 2 x 7 leaving 34-14=20, then * purchase 2 chocolate of type #3 for 2 x 10 leaving 20-20= 0.

He would thus satisfy 1 + 3 + 2 + 2 = 8 cows.

贝西和其他奶牛们都喜欢巧克力所以约翰准备买一些送给她们。奶牛巧克力专卖店里

有N种巧克力每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力调查显示

有Ci头奶牛喜欢第i种巧克力这种巧克力的售价是P。

约翰手上有B元预算怎样用这些钱让尽量多的奶牛高兴呢

输入格式

* Line 1: Two space separated integers: N and B

* Lines 2..N+1: Line i contains two space separated integers defining chocolate type i: P_i and C_i

输出格式

* Line 1: A single integer that is the maximum number of cows that Farmer John can satisfy

输入输出样例

输入 #1

5 50
5 3 
1 1 
10 4 
7 2 
60 1 

输出 #1

8 

 

万恶的贝西bushi 

其实真的没什么知识点纯纯贪心

上代码

# include <iostream>
# include <cstdio>
# include <algorithm> 
using namespace std;
# define int long long
int n,b;
struct node{
	int p,c;
}a[100005];
bool cmp(node x,node y){
	return x.p<y.p;
}
signed main(){
	scanf("%lld%lld",&n,&b);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].p,&a[i].c);
	}
	sort(a+1,a+1+n,cmp);
	int i=1,cnt=0;
	while(b){
		if (b>=a[i].p*a[i].c){
			b-=(a[i].p*a[i].c);
			cnt+=a[i].c;
		}else{
			int now=b/a[i].p;
			cnt+=now;
			b=0;
		}
		i++;
	}
	printf("%lld",cnt);
	return 0;
}

你不会看到这里就把代码复制走了吧

nonono

你会得到这样的结果

那到底是为什么呢注意看题目中pi的取值范围

小于等于10^18

long long根本吃不消的好吧

所以要上我们的unsigned long long

真AC代码

# include <iostream>
# include <cstdio>
# include <algorithm> 
using namespace std;
# define int unsigned long long
int n,b;
struct node{
	int p,c;
}a[100005];
bool cmp(node x,node y){
	return x.p<y.p;
}
signed main(){
	scanf("%lld%lld",&n,&b);
	for (int i=1;i<=n;i++){
		scanf("%lld%lld",&a[i].p,&a[i].c);
	}
	sort(a+1,a+1+n,cmp);
	int i=1,cnt=0;
	while(b){
		if (b>=a[i].p*a[i].c){
			b-=(a[i].p*a[i].c);
			cnt+=a[i].c;
		}else{
			int now=b/a[i].p;
			cnt+=now;
			b=0;
		}
		i++;
	}
	printf("%lld",cnt);
	return 0;
}