理论不应该发两篇相同的内容的
但是理论是理论，现实是现实，blog 会吃字数。
分析/正解
为什么会这样呢？
其实以上的操作就类似于冒泡排序，而在最劣情况下，交换数达到 n^2，序列长度就超了。
然后根据题解，是有更聪明的构造方法的。
我们令原本输入的 a 数组变为 c 数组，并将 a 数组最开始定义为 [1, 2, 3, …,n]。
将 b 每 n – 1 个分一段，每一段在上一次的基础上作修改。
这个过程可以看成是一个 p 指针一直在 [2,n] 上循环移动，每次移动后决定 a_1 是否与 a_p 进行交换，将最终的 a_p 加入 b 的末尾，并且最终将这个 a 数组变成 c 数组。
在上面的基础上，我们有一个贪心的策略。
- 若当前 a_1 \neq c_1 ，将 p 移动到 a_1 的目标位置（就是 c_p = a_1），并将 a_1 与 a_p 交换，使 a_1 归位。
-
若当前 a_1 = c_1，那么我们找到第一个 a_p \neq c_p 的位置，并将 a_1 与 a_p 交换，强制变成上面的那种情况。
（不太会的）正确性分析：
长度上：
- $a_1 = c_1$ 的情况出现的次数只与排列中环的个数有关，而这是 $\ln n + O(1)$ 的。
-
对于 a_1 \neq c_1 的情况，每次期望移动 \frac{n}{2} 步，所以总的移动次数是 \frac{n^2}{2} 级别的。
字符顺序上：
每次若不进行交换，那么当前输出时一定和上一次输出相隔 n – 1 个，满足要求。
若进行交换，那么这个 a_1 一定是因为前面原本要输出的时候突然被换掉，而在前面原本要输出位置，相隔距离就已经有 n – 1 了，放后面输出肯定距离也是满足要求的。
[Code]
#include
using namespace std;
const int File = 1;
#define FRE if(File)
const int N = 1005, M = 550000;
int n, a[N], c[N];
vector res;
int main()
{
FRE freopen("perm.in", "r", stdin);
FRE freopen("perm.out", "w", stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i ++)
{
a[i] = i;
scanf("%d", &c[i]);
res.push_back(i);
}
while (1)
{
int flag = 1;
if (a[1] != c[1])
{
for (int p = 2;p <= n;p ++)
{
if (c[p] == a[1])
{
swap(a[1], a[p]);
flag = 0;
}
res.push_back(a[p]);
}
}
else
{
for (int p = 2;p <= n;p ++)
{
if (a[p] != c[p])
{
swap(a[1], a[p]);
flag = 0;
}
res.push_back(a[p]);
}
}
if (flag)break;
}
for (int i = 1;i <= n; i ++)res.push_back(a[i]);
printf("%d\n", res.size());
for(auto i : res)printf("%d ", i);
return 0;
}
[T2/Unfound 6]
题面
[题目描述]
给定正整数 n，有两个长度为 n 的整数数列 {a_n}, {b_n}，请你找到两个非负整数 x, y 和一个非负整数数列 {$cn}，最小化 \sum{i=1}^n(|a_i-c_ix|+|b_i-c_iy|)$。
你只需要输出这个式子的最小值即可。
[输入格式]
第一行，一个正整数 n。
第二行，n 个非负整数 a_1, a_2, …, a_n。
第三行，n 个非负整数 b_1, b_2, …, b_n。
[输出格式]
一行，一个非负整数，表示答案。
[Sample 1]
input
1 3
2 1 1 4
3 5 1 4
output
1 4
[数据范围与子任务]
对于所有数据，1 \leq n \leq 30，0 \leq a_i, b_i \leq 10^8。
| 测试点 | $n \leq$ | 特殊性质 |
|---|---|---|
| 1 ~ 3 | $30$ | $a_i, b_i \leq 100$ |
| 4 ∼ 7 | $30$ | $a_i, b_i \leq 10^5$ |
| 8 | $30$ | $b_i = 0$ |
| 9 ~ 14 | $8$ | 无 |
| 15 ~ 17 | $25$ | 无 |
| 18 ~ 20 | $30$ | 无 |
闲话/部分分
考场上的 AC 代码全部使用了随机化。
评价是随机化真香。
但是后面加强数据了，成功把随机化全部卡掉。
所以建议大家还是学一学时钟打点来记时。