题解 P8475 「GLR-R3」雨水

wangzl · 2022-08-15 14:46:34 · 题解

题解 P8475 「GLR-R3」雨水

简要题意

感觉原题描述比较复杂QAQ
本题是给一个长度为 n 的序列 a，希望从中提取子序列 l（|l| 为偶数），并从前往后两两交换元素，将其放回原位置。使修改后的子序列的字典序最小。

基本思路：

先举个例子：a = \{\color{red}3\color{black},2,\color{red}1\color{black},\color{red}5\color{black},\color{red}4\color{black}\}，取出子序列 l=\{\color{green}3\color{black},\color{green}1\color{black},\color{blue}5\color{black},\color{blue}4\color{black}\}，两两交换后 l'=\{1,3,4,5\}，按原顺序放回原序列，变为 a'=\{1,2,3,4,5\}。显然，此时 a' 的字典序最小。
那么，我们该怎么移动序列呢？首先，要使字典序尽可能小，我们就要把最小的放在第一位，可以证明，如果使用其他的方法，最小的那个数没有排在第一位，那么处理后的序列一定不是字典序最小的子序列。因为是两两交换，假设 a_i 与 a_j 进行了第一次交换 (i<j)，那么下一次交换就要从 a_{j + 1} 开始，如果从 a_{i+1} 继续遍历进行交换，显然不符合我们两两依次交换的原则，是错误的交换方法。这样每一次交换后令 i=j+1 进行下一次交换，直到 i=n 为止，这样每一次贪心去寻找，找到的一定是最优解。

当查找时 a_i 后出现多个最小元素怎么办呢？我们应该交换最后一个。因为进行交换时的元素满足 a_i>a_j(i<j)，显然，我们要把更大的 a_i 放在最后那个最小元素的位置，才可以使答案字典序最小。
再举个例子：a=\{2,1,3,1,1\}，我们发现，当 i=1,a_i=2 时，其后最小值为 1，而可以交换的 j=2,4,5，交换后可以变为 a'=\{1,2,3,1,1\},a''=\{1,1,3,2,1\},a'''=\{1,1,3,1,2\}，可见与最后一个最小元素交换得到的字典序是最小的。所以，我们在遍历 a_{j_{\min}} 时，要自 n 向 i+1 倒序遍历。

• 注意：本题要求答案对 2^{64} 取模，unsigned long long 的自然溢出就等于对 2^{64} 的取模。

  \text{std:}

  #include<bits/stdc++.h>
  typedef unsigned long long ull;
  const int MAXN = 1e7; // Set a right value according to your solution.
  int n, kind;
  int a[MAXN + 1];
  ull sum; 
  namespace Generator {
  unsigned long long k1, k2;
  int thres;
  inline unsigned long long xorShift128Plus() {
      unsigned long long k3 = k1, k4 = k2;
      k1 = k4, k3 ^= (k3 << 23), k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
      return k2 + k4;
  }
  inline void generate() {
      for (int i = 1; i <= n; ++i) {
          a[i] = xorShift128Plus() % thres;
      }
  }
  }
  int main() {
  scanf("%d", &n);
  scanf("%llu %llu %d", &Generator::k1, &Generator::k2, &Generator::thres);
  Generator::generate();
  for (int i = 1; i <= n; ++i) {
      int minn = 0x7fffffff, sce;
      for (int j = n; j > i; --j) 
          if (a[j] < minn) 
          minn = a[j], sce = j;
      if (minn < 0x7fffffff && a[i] > a[sce])
          std::swap(a[i], a[sce]),
          i = sce;
  }
  for (int i = 1; i <= n; ++i) {
      sum = sum + (ull)i * a[i];
  }
  printf("%llu", sum);
  return 0;
  }

时间复杂度分析：本代码看似两重循环，但每次 i 从 j + 1 继续所以每个元素只被遍历 1 次，时间复杂度为 \mathcal{O(n)}。
有问题欢迎评论区留言哦！