P8444 题解

前言

题目传送门！

更好的阅读体验？

普及组月赛第二题。特殊数据好恶心啊，考试差点丢分了。

思路

贪心题，先给 \(a\) 数组排个序。

首先，肯定是买小于等于 \(w\) 的最大价格的物品。如果买不到，直接输出 \(0\)。

上面一点可以使用二分实现，速度快一点（直接用 STL 就行）。

然后，按价格从小到大枚举，见一个买一个。因为，只要可以买得起，根据贪心思想，买小的最划算。

另外，记得判 \(n = 1\) 的情况。不过貌似不特判也能 AC。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int inf = 2147483647;
int a[1000005];
int main()
{
	int n, w, cnt = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &w);
	sort(a+1, a+n+1);
	if (a[1] > w) {putchar('0'); return 0;} //如果最便宜的物品都买不起，还搞个屑啊。 
	if (n == 1) {putchar('1'); return 0;} //可以买得起的情况下，特判。 
	int pos = upper_bound(a+1, a+n+1, w) - a - 1;
	long long sum = 0; //注意此处需要使用 long long。 
	for (int i = 1; i <= n; i++)
    {
        sum += a[i];
	    if (sum > a[pos])
	    {
	        printf("%d", i-1); //钱超过了，说明当前物品卖不了。 
	        return 0;
	    }
    }
	return 0;
}

希望能帮助到大家！
首发：2022-07-27 19:37:26