自动搬运

查看原文

来自洛谷，原作者为

	wangzl HELLO!

搬运于2025-08-24 22:39:24，当前版本为作者最后更新于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)}$。
有问题欢迎评论区留言哦！