E题过了97%,请问有什么问题吗,求助
我这题是先交换下标,再交换数值
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 7;
typedef pair<int, int> PII;
int a[N], fa[N];
vector<PII> v[N];
vector<PII> q[N];
map<int, int> mp;
int vis[N];
int find (int x) {
if (x != fa[x]) return fa[x] = find(fa[x]);
return fa[x];
}
void merge (int x, int y) {
int fx = find(x), fy = find(y);
if (fx != fy) {
fa[fy] = fx;
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
fa[i] = i;
v[i].push_back({a[i], i});
}
for (int i = 1; i <= n - k; i++) {
merge(i, i + k);
v[fa[i]].push_back({a[i + k], i + k});
}
for (int i = 1; i <= k && i <= n - k; i++) {
int fx = find(i);
vector<PII> p;
for (auto it: v[fx]) {
p.push_back(it);
}
sort(p.begin(), p.end());
int idx = 0;
for (auto it: v[fx]) {
a[it.second] = p[idx++].first;
}
}
//for (int i = 1; i <= n; i++) cout << a[i] << " \n"[i == n];
for (int i = 1; i <= n; i++) {
mp[a[i]] = i;
fa[i] = i;
}
for (int i = 1; i <= n; i++) {
if (mp[a[i] - k] != 0) {
merge(i, mp[a[i] - k]);
}
//cout << find(i) << " \n"[i == n];
}
for (int i = 1; i <= n; i++) {
int fx = find(i);
//cout << fx << " \n"[i == n];
q[fx].push_back({a[i], i});
}
for (int i = 1; i <= n; i++) {
int fx = find(i);
if (vis[fx]) continue;
vis[fx] = 1;
vector<PII> p;
for (auto it: q[fx]) {
p.push_back(it);
}
sort(p.begin(), p.end());
int idx = 0;
for (auto it: q[fx]) {
a[it.second] = p[idx++].first;
}
}
int f = 1;
for (int i = 1; i < n; i++) {
//cout << a[i] << " \n"[i == n];
if (a[i] > a[i + 1]) f = 0;
}
if (f == 1) cout << "Yes" << "\n";
else cout << "No" << "\n";
return 0;
}

查看8道真题和解析