P8444 题解
2022/8/27 23:22:47
本文主要是介绍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
这篇关于P8444 题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?