这道题的思路是很好想的,就是按照结构体中的p(单位价格)从小到大排序,然后就根据预算进行减法,直到减到预算没有了或者所有的巧克力都卖光了。
但是这道题我原先错了好多遍,找不出原因,最后发现问题是出在了数据的范围上,一开始看到a[i].p(单位价格),a[i].c(一种巧克力的总数量),b(预算)的数据大小都是1e18,所以我所有数据都用的ll(long long),以为这样就没有问题了,可最后还是出了问题,看代码吧,问题有写出来。
#include <cstdio> #include <cstring> #include <string> #include <cmath> #include <iostream> #include <algorithm> #include <vector> #include <stack> #include <sstream> #include <map> #include <set> #include <queue> #include <stdlib.h> typedef long long ll; using namespace std; struct sss { ll p,c; }a[100005]; bool cmp (sss x,sss y) { return x.p<y.p; } int main () { ll n,b; 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); ll ans = 0; for (int i=1;i<=n;i++) { ll t=b/a[i].p; /*第一种方法:如果 预算/单位价格>=总个数 ,那么一定可以都买下来(正确)*/ if(b/a[i].p >= a[i].c) { ans += a[i].c; b-= a[i].p*a[i].c; } /*第二种方法:如果 预算>=单位价格*总个数,那么一定可以都买下来(错误)*/ /* b , a[i].p , a[i].c的大小都是1-1e18,如果a[i].c*a[i].p的话,最后的结果肯定会爆ll(long long),所以要用第一种方法,也就是除法,而不能用加法 */ // if(b >= a[i].c * a[i].p) // { // ans += a[i].c; // b -= a[i].p*a[i].c; // } else { ans+=t; break; } } printf("%lld\n",ans); return 0; }