排序不等式

排队打水

原题链接

按照装满水所需时间，让所有人从小到大排队。

证明：

假设排队的序列为 t1,t2,… ,ti,ti+1,… ,tnt_1, t_2, \dotso, t_i, t_{i+1}, \dotso, t_n。

总等待时间=t1⋅(n−1)+t2⋅(n−2)+⋯+tn−1总等待时间 = t_1 \cdot (n-1) + t_2 \cdot (n-2) + \dotsb + t_{n-1}

其中第 i 和第 i + 1 个人没有按照从小到大的顺序排队，ti>ti+1t_i > t_{i+1}

此时这两人等待时间为 tit_{i}

而如果让第 i + 1 个人排在第 i 个人前面，这两人的等待时间为 ti+1t_{i+1}，显然优于交换前的等待时间，优化了 ti−ti+1t_i - t_{i+1} 的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int t[N];
int main() {
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> t[i];
  }
  sort(t, t + n);
  long long res = 0;
  for (int i = 0; i < n; i++) res += t[i] * (n - i - 1);
  cout << res << endl;
  return 0;
}

绝对值不等式

货仓选址

原题链接

选取的位置坐标是中位数。

已知直线上的一组点，坐标为 a1,a2,… ,aia_1, a_2, \dotso, a_i，寻找一个点，使得这个点距离其他点的距离之和最小。
设该点的坐标为 x。

f(x)=∣x−a1∣+∣x−a2∣+⋯+∣x−ai∣f(x) = |x - a_1| + |x - a_2| + \dotsb + |x - a_i| minimize 这个函数

f(x)=∣x−a1∣+∣x−ai∣+∣x−a2∣+∣x−ai−1∣+⋯f(x) = |x - a_1| + |x - a_{i}| + |x - a_2| + |x - a_{i-1}| + \dotsm

考虑两个点 a、b 的情况，只有当 x 选在 a、b 之间时，距离最小，为 b - a。观察上式，x 需要选在 a1∼aia_1 \sim a_{i} 之间、a2∼ai−1a_2 \sim a{i-1} 之间，直到最中间的两个点之间，如果是奇数，就选择中位数的坐标位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <iostream>
using namespace std;

const int N = 1e5 + 10;
int a[N];
int n;

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) cin >> a[i];
  sort(a, a + n);
  int res = 0;
  for (int i = 0; i < n; i++) {
    res += abs(a[i] - a[n / 2]);
  }
  cout << res << endl;
  return 0;
}

推公式

耍杂技的牛

算法：

按照 w[i] + s[i] 从小到大排序，最大危险系数一定最小。

证明：

证明思路类似于排队打水问题。假设有一处逆序，wi+si>wi+1+si+1w_i + s_i > w_{i+1} + s{i+1}。

- 第 i 个位置 第 i + 1 个位置
交换前 w1+w2+⋯+wi−1−siw_1 + w_2 + \dotsb + w_{i-1} - s_i w1+w2+⋯+wi−si+1w_1 + w_2 + \dotsb + w_{i} - s_{i+1}
交换后 w1+w2+⋯+wi−1−si+1w_1 + w_2 + \dotsb + w_{i-1} - s_{i+1} w1+w2+⋯+wi−1+wi+1−siw_1 + w_2 + \dotsb + w_{i-1} + w_{i+1} - s_{i}

删掉每一个表达式中相同的项，每项再加上 si+si+1s_i + s{i+1}

- 第 i 个位置 第 i + 1 个位置
交换前 si+1s_{i+1} wi+siw_i + s_i
交换后 sis_i wi+1+si+1w_{i+1} + s_{i+1}

因为 wi+si>wi+1+si+1w_i + s_i > w_{i+1} + s{i+1}，wi>=1w_i >= 1，所以 wi+si>max(si,wi+1+si+1)w_i + s_i > max(s_i, w_{i+1} + s_{i+1})，即 max(si,wi+1+si+1)<max(si+1,wi+si)max(s_i, w_{i+1} + s_{i+1}) < max(s_{i+1}, w_i + s_i)，所以交换之后，危险系数的最大值会变小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
using namespace std;
typedef pair<int, int> PII;

const int N = 50010;

int n;
PII cow[N];

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int w, s;
    cin >> w >> s;
    cow[i] = {w + s, w};
  }
  sort(cow, cow + n);
  int res = -2e9, sum = 0;
  for (int i = 0; i < n; i++) {
    int w = cow[i].second, s = cow[i].first - w;
    res = max(res, sum - s);
    sum += w;
  }
  cout << res << endl;
  return 0;
}