题解：P11096 [ROI 2022 Day 1] 体育课

Duanhen · 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;
}