「BZOJ2014」[Usaco2010 Feb] Chocolate Buying
Description
贝西和其他奶牛们都喜欢巧克力，所以约翰准备买一些送给她们。奶牛巧克力专卖店里
有N种巧克力，每种巧克力的数量都是无限多的。每头奶牛只喜欢一种巧克力，调查显示，
有Ci头奶牛喜欢第i种巧克力，这种巧克力的售价是P。
约翰手上有B元预算，怎样用这些钱让尽量多的奶牛高兴呢？下面举个例子：假设约翰
有50元钱，商店里有S种巧克力：
|
巧克力品种
|
单价
|
高兴的奶牛数量
|
|
1
2 3 4 5 |
5
1 10 7 60 |
3
1 4 2 1 |
显然约翰不会去买第五种巧克力，因为他钱不够，不过即使它降价到50，也不该选择
它，因为这样只会让一头奶牛高兴，实在太浪费了。最好的买法是：第二种买1块，第一种
买3块，第四种买2块，第三种买2块，正好用完50元，可以让1+3+2+2=8头牛高兴。
Input
第一行：两个用空格分开的整数：N和B，1<=N≤100000，1≤B≤10^18
第二行到N+1行：第i+l行，是两个用空格分开的整数：Pj和Ci，1≤Pi，Ci≤10^18
Output
第一行：一个整数，表示最多可以让几头奶牛高兴
Sample Input
5 50
53
11
10 4
7 2
60 1
53
11
10 4
7 2
60 1
Sample Output
8
题解
贪心。。。
描述有点问题，应该是每个巧克力的价格和购买上限
那么显然优先买便宜的
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #include<set> #include<queue> #include<map> #define pa pair<int,int> #define mod 1000000007 #define inf 1000000000 #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll b,ans; struct data{ll p,c;}a[100005]; bool operator<(data a,data b) { return a.p<b.p; } int main() { n=read();b=read(); for(int i=1;i<=n;i++) a[i].p=read(),a[i].c=read(); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { ll t=min(a[i].c,b/a[i].p); ans+=t; b-=a[i].p*t; } printf("%lld\n",ans); return 0; } |
计数器 9860053
OI 课件=>
OI 课件=>
OAO