排序不等式

3.排序不等式

AcWing 913.排队打水

实现思路：

假设各个同学的打水时间为：3 6 1 4 2 5 7 并且就按照这个顺序来打水。 当第一个同学打的时候，后面所有同学都要等他，所以等待的总时长要加上一个3 * 6，第二个同学打的时候，后面所有同学也都要等他，所以要加上个6 * 5，以此类推，所有同学等待的总时长为3 * 6 + 6 * 5 + 1 * 4 + 4 * 3 + 2 * 2 + 5 * 1

假设各个同学打水花费的时长为 t1，t2，t3，…，tn，则按照次序打水，总的等待时长为：t1 * (n-1) + t2 * (n-2) + ... + tn * 1。

可以看出，当打水顺序按照花费时间从小到大排序时，所得的等待时间最小

证明

采用反证法（调整法），假设最优解不是按照从小到大的顺序，则必然存在2个相邻的人，前一个人打水时长比后一个大，即必然存在一个位置i，满足t_i > t_i+1，那我们尝试把这两个同学的位置交换，看看对总的等待时长有什么影响，这两个同学的交换，只会影响他们两的等待时长，不会影响其他同学的等待时长。 交换前，这部分等待时长为t_i * (n-i) + t_i+1 * (n-i-1)，交换后，这部分等待时长为t_i+1 * (n-i) + t_i * (n-i-1)，容易算得，交换后的等待时长变小了，则该方案不是最优解，矛盾了。则最优解就是按照从小到大的顺序依次打水。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=100010;
int n,t[N];

int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>t[i];
    LL res=0;//数据范围比较大，防止溢出，使用LL
    sort(t,t+n);
    for(int i=0;i<n;i++) res+=t[i]*(n-i-1);
    cout<<res;
    return 0;
}