自动搬运

查看原文

来自洛谷，原作者为

	Duanhen A single spark can start a prairie fire.

搬运于2025-08-24 23:04:12，当前版本为作者最后更新于2024-12-31 15:37:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

对于每一对 $i$ 和 $j$，用 $d(i, j)$ 表示选择从第 $l$ 到第 $r$ 位置 $(1 \le l \le r \le n)$ 的一段队列并进行排序可以使刚开始在位置 $i$ 和 $j$ 上的学生之间的距离最大，而我们需要计算 $\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}d(i,j)$。

解题思路

对于某一对 $i$ 和 $j$，第一种排序情况便是将所有元素都选中，此时两者的距离变为 $|p_i-p_j|$，但是这并不一定的最优情况。

而我们可以通过贪心的思想来找到最优解。

对与 $i$ 来说，想要离 $j$ 更远，就必须将它前面比它大的元素都选中，使这些元素排在它后面，而元素的个数就是增加的距离。而对于 $j$ 来说，情况则相反，需要找出它后面比它小的元素，让这些元素排在它前面，元素的个数就是增加的距离。

所以我们可以先预处理出对于每一个元素，它前面比它大的元素个数和后面比它小的元素个数。在求解时，我们可以比较 $i$ 前面的大元素个数和 $j$ 后面的小元素个数，哪个大我们就选哪个，然后再跟全选的结果 $|p_i-p_j|$ 作比较，就可以得出最优解。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll p[3010], a[3010], b[3010], n, res;

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> p[i];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j < i; j++) {
      if (p[j] > p[i]) a[i]++;
      if (p[j] > p[i]) b[j]++;
    }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++) {
      ll tp = max(a[i], b[j]) + (j - i);
      tp = max(tp, abs(p[i] - p[j]));
      res += tp;
    }
  cout << res;
  return 0;
}