社区讨论

Yet Another 正确性求助

PPikachuQAQ
灌水区参与者 1已保存回复 2

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@m2lwu2u1
此快照首次捕获于
2024/10/23 21:28
去年
此快照最后确认于
2025/11/04 16:24
4 个月前
查看原帖
前传
求助一下两份代码的复杂度正确性:
swap 思路: 将相等的全部 swap 走.
这一份时间复杂度很小概率假: 峰值时间 166ms
CPP
#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5 + 2;

int n, a[kN], b[kN];
map<int, int> bt, ct;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bt[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        ct[b[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (bt[a[i]] + ct[a[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (bt[b[i]] + ct[b[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    cout << "Yes\n";
    reverse(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            reverse(b + i, b + n + 1);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            for (int j = 1; j <= n; j++) {
                if (a[j] != b[i] && b[i] != b[j]) {
                    swap(b[i], b[j]);
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }

    return 0;
}
这一份时间复杂度很大概率假: 峰值时间 991ms
CPP
#include <bits/stdc++.h>

using namespace std;

const int kN = 2e5 + 2;

int n, a[kN], b[kN];
map<int, int> bt, ct;

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        bt[a[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        ct[b[i]]++;
    }
    for (int i = 1; i <= n; i++) {
        if (bt[a[i]] + ct[a[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (bt[b[i]] + ct[b[i]] > n) {
            cout << "No\n";
            exit(0);
        }
    }
    cout << "Yes\n";
    reverse(b + 1, b + n + 1);
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            for (int j = 1; j <= n; j++) {
                if (a[j] != b[i] && b[i] != b[j]) {
                    swap(b[i], b[j]);
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        cout << b[i] << ' ';
    }

    return 0;
}

回复

共 2 条回复，欢迎继续交流。

正在加载回复...