526互联

Codeforces Round 672 (Div. 2) A. Cubes Sorting

发布时间 2023-10-13 22:51:15作者: zsxuan

有 \(n\) 个方块，第 \(i\) 个方块重量为 \(a_i\) 。需要使方块按照非降序排列摆放。在每一步操作中，可以交换任意相邻的两块方块。询问可以使所有方块按照非降序排序的最小操作数 \(p\) 是否 \(\frac{n \cdot (n - 1)}{2}\) 。

考虑一个事实，对于任意第 \(i\) 个方块，它需要和右边的相邻方块交换的次数为 \(inversion(a_i)\) 。如果过程中遇到了 \(a_j > a_i\) ，可以假设第 \(j\) 个方块提前右移了。于是总的交换次数为 \(p = \sum_{i = 1}^{n} inversion(a_i)\) 。

\(a_i\) 的范围很大，于是可以使用离散化+树状数组求解出 \(p\) 。注意不能有 \(0\) 的出现。

然后可以直接用 \(p\) 与 \(\frac{n \cdot (n - 1)}{2}\) 进行比较。

view1 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<class T>
struct BIT{
	std::vector<T> c;
	int sz;
	void init(int s) {
		sz = s;
		c.assign(s + 1, 0);
	}
	void add(int x, T s) {
		assert(x > 0);
		for ( ; x <= sz; x += x & (-x))
			c[x] += s;
	}
	T query(int x) {
		T s = 0;
		for ( ; x; x -= x & (-x))
			s += c[x];
		return s;
	}
};
BIT<int> c;
void solve(){
	int n; std::cin >> n;
	c.init(n+5);
	std::vector<int> a(n+1);
	std::vector<int> nums(n);
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
		nums[i-1] = a[i];
	}
	std::sort(nums.begin(), nums.end());
	nums.erase(std::unique(nums.begin(),nums.end()),
		nums.end());
	ll cnt = 0;
	for (int i = n; i; --i) {
		int x = std::lower_bound(nums.begin(), nums.end(), a[i]) - nums.begin() + 2;
		cnt += c.query(x - 1);
		c.add(x, 1);
	}
	// std::cout << cnt << '\n';
	std::cout << (cnt >= 1LL * n * (n - 1) / 2 ? "NO" : "YES") << '\n';
}
		                
int main() {
	#ifndef ONLINE_JUDGE
    freopen("IO/in", "r", stdin); freopen("IO/out", "w", stdout);
	#endif 
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}

是否有更优的方法？