A18398. 排排坐
填空题
困难
知识点
题目描述
排排坐
题目描述
老师正在和小朋友们分糖果。
小朋友们先在自己的手上写一个数字，然后坐成一排。
老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。
请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。
输入格式
输入 2 行，
第一行为一个正整数 n，表示小朋友的个数；
第二行为 n 个正整数 a1,a2,...,an，表示小朋友们手上的数字，整数之间以空格分隔。
输出格式
输出一个整数，表示小朋友们可能分到的最大糖果总数量。
输入样例
5
7 5 8 9 3输出样例
111样例解释
小朋友安排座位后从左向右每人手上数字依次是： 9,8,7,5,3。
这时可以得到最多的糖果：9+(9+8)+(9+8+7)+(9+8+7+5)+(9+8+7+5+3)=111 。
参考答案
#include <iostream>
using namespace std;
int a[1010];
void bubble_sort(int n) {
for (int i = 0; i < n; ++i) {
for (int j = 1; j < n - i; ++j) {
if (a[j - 1] < a[j])
swap(a[j - 1], a[j]);
}
}
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
cin >> a[i];
bubble_sort(n);
int ans = 0, sum = 0;
for (int i = 0; i < n; ++i) {
sum += a[i];
ans += sum;
}
cout << ans << endl;
return 0;
}
上一题
下一题