P17010 [GESP202606 五级] 排排坐
题目描述
老师正在和小朋友们分糖果。
小朋友们先在自己的手上写一个数字，然后坐成一排。
老师分发糖果的规则是：每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。
现在小朋友们都已经在自己手上写上了数字。
请帮小朋友们安排合适的座位顺序，使得小朋友们分到的糖果总量最大，输出这个最大值。
输入格式
输入222行，
第一行为一个正整数nnn，表示小朋友的个数；
第二行为nnn个正整数a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1,a2,⋯,an，表示小朋友们手上的数字，整数之间以空格分隔。
输出格式
输出一个整数，表示小朋友们可能分到的最大糖果总数量。
输入输出样例 #1
输入 #1
5 7 5 8 9 3输出 #1
111说明/提示
样例解释
小朋友安排座位后从左向右每人手上数字依次是：9,8,7,5,39, 8, 7, 5, 39,8,7,5,3。
这时可以得到最多的糖果：(9)+(9+8)+(9+8+7)+(9+8+7+5)+(9+8+7+5+3)=111(9) + (9 + 8) + (9 + 8 + 7) + (9 + 8 + 7 + 5) + (9 + 8 + 7 + 5 + 3) = 111(9)+(9+8)+(9+8+7)+(9+8+7+5)+(9+8+7+5+3)=111。
数据范围
1≤n≤10001 \le n \le 10001≤n≤1000，1≤ai≤10001 \le a_i \le 10001≤ai≤1000。
题解
本题要求重新排列数字，使得每个位置的前缀和之和最大。
对于某个排列p1,p2,…,pnp_1, p_2, \dots, p_np1,p2,…,pn，总糖果数为：
S=p1+(p1+p2)+(p1+p2+p3)+⋯+(p1+⋯+pn) S = p_1 + (p_1+p_2) + (p_1+p_2+p_3) + \dots + (p_1+\dots+p_n)S=p1+(p1+p2)+(p1+p2+p3)+⋯+(p1+⋯+pn)
化简可得：
S=n⋅p1+(n−1)⋅p2+(n−2)⋅p3+⋯+1⋅pn S = n \cdot p_1 + (n-1) \cdot p_2 + (n-2) \cdot p_3 + \dots + 1 \cdot p_nS=n⋅p1+(n−1)⋅p2+(n−2)⋅p3+⋯+1⋅pn
也就是说，越靠左的数字被计算的次数越多，因此为了让总和最大，应该把最大的数字放在最左边，次大的放在第二位，依此类推。所以只需要将原数组从大到小排序，然后计算前缀和并累加，即可得到最大值。
时间复杂度O(nlogn)O(n \log n)O(nlogn)，n≤1000n \le 1000n≤1000，完全可行。 空间复杂度O(n)O(n)O(n)。
带注释的源代码
#includeusingnamespacestd;intn;inta[1005];// 存储小朋友手上的数字intans=0;// 最大糖果总数intmain(){cin>>n;// 读入小朋友个数// 读入所有数字for(inti=1;i<=n;i++){cin>>a[i];}// 按照从大到小排序，使得大数放在左侧，贡献更多次sort(a+1,a+n+1,greater<int>());// 累加前缀和，并同时将前缀和加入答案for(inti=1;i<=n;i++){a[i]+=a[i-1];// 此时 a[i] 变为原数组前 i 个数的和（即第 i 个小朋友得到的糖果数）ans+=a[i];// 累加每个小朋友的糖果数}// 输出最大糖果总数cout<<ans;return0;}