桶排序练习题：石沉大海 - 算法竞赛 CF 问题

"问题 CF: 桶排序课堂练习题五：石沉大海\n内存限制：128 MB\n时间限制：1.000 S\n评测方式：文本比较\n命题人：haoxuanlls\n提交：3\n解决：3\n题目描述\n小珅同学是一个不擅长数学的女孩子，她的数学试卷极为凄惨。但是她长于语文，尤善活用成语。她想到了"石沉大海"一词，深得启发。于是决定用石头压住数学试卷，沉入海底，以免被别人看到。\n小珅的试卷可以承载 w 重量的石头，也就是说，如果用恰好 w 重量的石头压住试卷，试卷犹可浮于水面，超过 w 重量则会沉入海底。小珅有 n 块石头，她想知道她至少需要多少块石头才能完成"石沉大海"的大业。\n题目保证 n 块石头总重量大于 w，且最多需要 500 块石头。\n\n输入\n输入共 n+1 行:\n第 1 行，两个正整数 w, n，分别表示试卷可以承载的重量和小珅所持的石头个数；\n之后 n 行，每行 1 个正整数，依次表示 n 块石头的重量。\n一定用桶排序\nc++代码内容：c++\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint main() {\n int w, n;\n cin >> w >> n;\n vector<int> stones(n);\n for (int i = 0; i < n; i++) {\n cin >> stones[i];\n }\n vector<int> bucket(w + 1, 0);\n for (int i = 0; i < n; i++) {\n bucket[stones[i]]++;\n }\n int cnt = 0;\n int sum = 0;\n for (int i = w; i >= 1; i--) {\n if (bucket[i] == 0) {\n continue;\n }\n int num = min(bucket[i], (w - sum) / i);\n cnt += num;\n sum += num * i;\n if (sum == w) {\n break;\n }\n }\n cout << cnt << endl;\n return 0;\n}\n