P17010 [GESP202606 五级] 排排坐题目描述老师正在和小朋友们分糖果。小朋友们先在自己的手上写一个数字然后坐成一排。老师分发糖果的规则是每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。现在小朋友们都已经在自己手上写上了数字。请帮小朋友们安排合适的座位顺序使得小朋友们分到的糖果总量最大输出这个最大值。输入格式输入222行第一行为一个正整数nnn表示小朋友的个数第二行为nnn个正整数a1,a2,⋯ ,ana_1, a_2, \cdots, a_na1,a2,⋯,an表示小朋友们手上的数字整数之间以空格分隔。输出格式输出一个整数表示小朋友们可能分到的最大糖果总数量。输入输出样例 #1输入 #15 7 5 8 9 3输出 #1111说明/提示样例解释小朋友安排座位后从左向右每人手上数字依次是9,8,7,5,39, 8, 7, 5, 39,8,7,5,3。这时可以得到最多的糖果(9)(98)(987)(9875)(98753)111(9) (9 8) (9 8 7) (9 8 7 5) (9 8 7 5 3) 111(9)(98)(987)(9875)(98753)111。数据范围1≤n≤10001 \le n \le 10001≤n≤10001≤ai≤10001 \le a_i \le 10001≤ai≤1000。题解本题要求重新排列数字使得每个位置的前缀和之和最大。对于某个排列p1,p2,…,pnp_1, p_2, \dots, p_np1,p2,…,pn总糖果数为Sp1(p1p2)(p1p2p3)⋯(p1⋯pn) S p_1 (p_1p_2) (p_1p_2p_3) \dots (p_1\dotsp_n)Sp1(p1p2)(p1p2p3)⋯(p1⋯pn)化简可得Sn⋅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_nSn⋅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)。带注释的源代码#includebits/stdc.husingnamespacestd;intn;inta[1005];// 存储小朋友手上的数字intans0;// 最大糖果总数intmain(){cinn;// 读入小朋友个数// 读入所有数字for(inti1;in;i){cina[i];}// 按照从大到小排序使得大数放在左侧贡献更多次sort(a1,an1,greaterint());// 累加前缀和并同时将前缀和加入答案for(inti1;in;i){a[i]a[i-1];// 此时 a[i] 变为原数组前 i 个数的和即第 i 个小朋友得到的糖果数ansa[i];// 累加每个小朋友的糖果数}// 输出最大糖果总数coutans;return0;}
