这道题的思路是很好想的,就是按照结构体中的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;
}


京公网安备 11010502036488号