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;
}

全部评论
此贴完结,这是错误做法,先交换下标再交换数值,出题人题解下面有hack数据
点赞 回复 分享
发布于 02-16 18:31 重庆

相关推荐

11-03 13:18
门头沟学院 Java
包行:平时怎么刷算法题的哇,字节的手撕听说都很难
字节跳动工作体验
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务