[USACO 2010 Feb S]Chocolate Buying

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.

C++14(g++5.4) 解法, 执行用时: 145ms, 内存消耗: 2024K, 提交时间: 2019-11-09 21:38:27

#include<iostream>
#include<algorithm>
using namespace std;
int n;
unsigned long long ans,v;
struct cz{
    unsigned long long p,c;
}a[100005];
bool cmp(cz x,cz y){return x.p<y.p;}
int main(){
    cin>>n>>v;
    for(int i=1;i<=n;i++)cin>>a[i].p>>a[i].c;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++){
        if(v>a[i].p*a[i].c){v=v-a[i].p*a[i].c;ans+=a[i].c;}
        else{ans+=v/a[i].p;break;}
    }
    cout<<ans;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 170ms, 内存消耗: 4432K, 提交时间: 2019-11-12 16:35:24

#include<iostream>
#include<algorithm>
using namespace std;
struct node{
	long long v,w;
}a[100008];
bool cmp(node a,node b){
	return a.v<b.v;
}
int main(){
	long long n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		cin>>a[i].v>>a[i].w;
	}
	sort(a,a+n,cmp);
	long long ans=0;
	for(int i=0;i<n;i++){
		if(m/a[i].v<a[i].w){
			ans=ans+m/a[i].v;
			break;
		}
		m=m-a[i].v*a[i].w;
		ans=ans+a[i].w;
	}
	cout<<ans<<endl;
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 733ms, 内存消耗: 21288K, 提交时间: 2019-11-11 17:20:03

n, m = map(int, input().split())
a = []
for i in range(n):
    a.append(tuple(list(map(int, input().split()))))
a.sort(key = lambda x : x[0])
ans = 0
for i in a:
    if m < i[0] * i[1]:
        ans += m // i[0]
        break
    ans += i[1]
    m -= i[0] * i[1]
print(ans)

详情