C++ 雪人部落储备粮分配问题：算法解析与代码实现

雪人部落储备粮分配问题：算法解析与代码实现/n/n在寒冷的冬季，当雪人部落遇到了食物匮乏的季节，会拿出储备粮接济吃不饱饭的雪人家庭。现在雪人部落中有n个家庭，每个家庭有自己的储备粮数量。雪人部落会计算当前所有雪人家庭储备粮的平均值，然后额外提供一些粮食给予低于平均值的雪人家庭，使其粮食储量达到计算的平均值。请问雪人部落一共需要提供多少储备粮。/n/n输入: /n共两行。/n/n第一行为一个整数n(n<=105)，表示有n个雪人家庭。/n/n第二行为n个整数，表示每个雪人家庭的储备粮数量。/n/n输出: /n一个数，表示雪人部落要额外提供的储备粮数量。/n/n输入样例: /n5/n1 2 3 4 5/n/n输出样例: /n3/n/n算法1 (暴力枚举) $O(n)$/n/n先对所有家庭的储备粮求和，再求平均值，最后再遍历一遍，统计需要提供的储备粮的数量。/n/n时间复杂度:/n统计和，遍历数组，所以时间复杂度是$O(n)$。/n/nC++ 代码:/ncpp/n#include <iostream>/nusing namespace std;/n/nint main() {/n int n;/n cin >> n;/n int sum = 0;/n int a[n];/n for (int i = 0; i < n; i++) {/n cin >> a[i];/n sum += a[i];/n }/n double avg = (double)sum / n;/n int need = 0;/n for (int i = 0; i < n; i++) {/n if (a[i] < avg) {/n need += avg - a[i];/n }/n }/n cout << need << endl;/n return 0;/n}/n/n/n算法2 (排序算法) $O(n /log n)$/n/n首先对所有家庭的储备粮进行降序排序，计算总的储备粮的和，遍历家庭储备粮数组，当家庭储备粮小于平均值时，这个家庭需要额外提供的数量就是平均值与当前家庭储备粮数的差值，然后统计需要的储备粮。/n/n时间复杂度:/n排序算法的复杂度是$O(n/log n)$，计算和和遍历数组，所以时间复杂度是$O(n)$。/n/nC++ 代码:/ncpp/n#include <iostream>/n#include <algorithm>/nusing namespace std;/n/nint main() {/n int n;/n cin >> n;/n int a[n];/n int sum = 0;/n for (int i = 0; i < n; i++) {/n cin >> a[i];/n sum += a[i];/n }/n sort(a, a + n, greater<int>()); // 降序排序/n double avg = (double)sum / n;/n int need = 0;/n for (int i = 0; i < n; i++) {/n if (a[i] < avg) {/n need += avg - a[i];/n }/n }/n cout << need << endl;/n return 0;/n}/n/n/n总结:/n/n两种算法都能够解决雪人部落储备粮分配问题，暴力枚举算法简单易懂，但时间复杂度较高；排序算法需要额外的排序操作，但时间复杂度更优。选择哪种算法取决于你的具体需求和数据规模。/n