题目传送门!
更好的阅读体验?
普及组月赛第二题。特殊数据好恶心啊,考试差点丢分了。
贪心题,先给 \(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