题目描述

https://www.acwing.com/problem/content/description/915/

算法1

(贪心) $O(nlogn)$

证明：
考虑到总时间 = $t1 * (n - 1) + t2 * (n - 2) + t3 * (n - 1) * … * tn * (n - 1)$
贪心策略：将数列排好序得到的答案为最优
反证法：当未排序时，必然存在两个数$ti, tj(ti > tj, i = j - 1)$,由于相邻数字交换不影响其他时间，所以
此时对于排序前：$ti * (n - i) + tj * (n - i - 1)$ ①
排序后: $tj * (n - i) + ti * (n - i - 1)$ ②
① - ② 得 $ti - tj > 0$
也就是说排序前的时间比排序后的时间大，矛盾

参考文献

https://www.acwing.com/video/339/

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
typedef long long LL;
LL a[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];

    sort(a, a + n);

    LL res = 0;
    for(int i = 0; i < n; i ++) res += a[i] * (n - i - 1);
    printf("%lld\n", res);
    return 0;
}