专栏文章

题解：CF220C Little Elephant and Shifts

___ikun__horro__
CF220C题解参与者 3已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miqmgoy0
此快照首次捕获于
2025/12/04 07:12
3 个月前
此快照最后确认于
2025/12/04 07:12
3 个月前
查看原文

Solution

我们先来观察样例 #2：
CPP
4
2 1 3 4
3 4 2 1
先求出 bb 数组每一次滚动和 aa 数组每个数位置的差值（不取绝对值）：
轮数 \ 数字1\bm 12\bm 23\bm 34\bm 4
1\bm 1−2-2−2-22\color{red} 222
2\bm 2−1-1−1-1−1\color{red} -13\color{blue} 3
3\bm 3000\color{green} 0000\color{blue} 0
4\bm 411−3\color{green} -31111
容易发现，每两轮相邻的操作间，n−1n-1 个数字加上 11，还有一个数字减去了 (n−1)(n-1)。
我们可以用一个 mutiset\text {mutiset} 维护所有的位置差值。而且大部分的数字都是加上 11 的，所以我们可以用一个偏移量 dd，第 ii 轮的偏移量 d=i−1d=i-1。使用 x−dx-d 来维护 xx 这个数，这样每轮只需要将一个数减去 nn。
轮数 \ 数字1\bm 12\bm 23\bm 34\bm 4
1\bm 1−2-2−2-22\color{red} 222
2\bm 2−2-2−2-2−2\color{red} -22\color{blue} 2
3\bm 3−2-2−2\color{green} -2−2-2−2\color{blue} -2
4\bm 4−2-2−4\color{green} -4−2-2−2-2
这样，我们每一轮只需取出一个最接近 −d-d 的数 xx，输出 ∣x+d∣| x+d | 即可。
那么每次到底要让哪一个数减去 nn 呢？观察一下，第 ii 轮就让 bib_i 所对应的数减去 nn。这样就做完了。
注意：multiset\text{multiset} 去掉数字时 erase\text{erase} 函数里要放指针，否则会删除值相同的所有的数。

Code

CPP
#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 1e5 + 5;

int n, a[N], b[N], p[N];
multiset<int> mango;

inline void sol() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[a[i]] = i;
	}

	auto calc = [=] (int x) {
		return p[b[x]] - x;
	};

	for (int i = 1; i <= n; i++) {
		cin >> b[i];
		mango.insert(calc(i));
	}

	for (int i = 1; i <= n; i++) {
		int delta = i - 1;

		// for (auto i : mango) {
		// 	cout << i << " ";
		// }
		// cout << "\n";
		// for (auto i : mango) {
		// 	cout << i + delta << " ";
		// }
		// cout << "\n";

		auto it = mango.lower_bound(-delta);
		int Min = 0x3f3f3f3f3f3f3f3f;

		if (it != mango.end()) {
			Min = min(Min, abs(*it + delta));
		}
		if (it != mango.begin()) {
			Min = min(Min, abs(*(--it) + delta));
		}

		cout << Min << "\n";

		it = mango.lower_bound(calc(i));

		if (it != mango.end()) mango.erase(it);
		mango.insert(calc(i) - n);

		// cout << "del " << calc(i) + delta << "\n";
		// cout << "add " << calc(i) - n + delta + 1 << "\n";
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	// init();
	int T = 1;
	// cin >> T;
	while (T--) sol();
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...