不等式

排序不等式

原题链接:913. 排队打水 - AcWing题库

排队打水，每人耗时不等，要怎么打总时间最短

实现

由于比较简单直接写实现

但是再简单也要理一遍逻辑 当存在非升序排序的某个组合时，一定有相邻的两个数是降序的，它们令之后的所有人都等它们打好水，而打水时长为： t[i] * 后面的人数 当降序时，必有t[i] * n + t[i+1] * (n-1) > t[i+1] * n + t[i] * (n-1) 因为t[i] > t[i+1]

得证

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1e5 + 10;
 
typedef long long LL;
 
 
int main()
{
    int n;
    cin >> n;
    
    int t[N];
    
    for(int i = 0; i < n ;i ++)
    {
        cin >> t[i];
    }
    
    sort(t, t + n);
    
    LL res = 0;
    for(int i = 0; i < n; i ++)
    {
        res += t[i] * (n - i - 1);
    }
    
    cout << res << endl;
    
    return 0;
}

注意数据范围

绝对值不等式

原题链接：104. 货仓选址 - AcWing题库

题意：数轴上，仓库建在哪里到各个商场的距离之和最小

思路

画图看

如果只有两个商场：

• 在两点中间的话，距离是两点的距离
• 在两点之外，距离大于两点距离

结论：奇数的话，在中点的商场；偶数的话，在中间两商场之间

实现

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int N = 1e6 + 10;
typedef long long LL;
 
int a[N];
 
int main()
{
    int n;
    cin >> n;
    
    for(int i = 0;  i < n; i ++)
    {
        cin >> a[i];
    }
    
    sort(a, a + n);
    
    LL ans = 0;
    //如果奇数
    if(n & 1)
    {
        for(int i = 0, j = n - 1; i <= n / 2; i ++, j --)
            ans += a[j] - a[i];
    }
    else
    {
        for(int i = 0, j = n - 1; i < n / 2; i ++, j --)
            ans += a[j] - a[i];
    }
    
    cout << ans << endl;
    
    return 0;
}