有 \(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;
}
是否有更优的方法？