8.8 美团笔试AK代码

题目较为简单，但是第一题也是醉了，交了好多次才完全通过。😂😂😂

第一题：直接排序

#include <bits/stdc++.h>
using namespace std;
void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    sort(a.begin(), a.end());
    if (k == 0) {
        cout << "YES\n";
        cout << 1 << '\n';
    } else {
        int ans = a[k - 1] + 1;
        int t = lower_bound(a.begin(), a.end(), ans) - a.begin();
        if (ans <= n && t == k) {
            cout << "YES\n";
            cout << ans << '\n';
        } else {
            cout << "NO\n";
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

第二题：简单的字符串处理

import sys


line = sys.stdin.readline().strip()
pre = "$"
ans = []
for c in line:
    if c != pre and c != " ":
        ans.append(c)
    if c != " ":
        pre = c
print("".join(ans))

第三题：有序集合（注意数据溢出）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, x;
    long long ans = 0;
    set<int> S;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x;
        auto it = S.lower_bound(x);
        if (it != S.begin()) {
            --it;
            ans += 1LL * i * (*it);
        }
        S.emplace(x);
    }
    cout << ans << '\n';
    return 0;
}

第四题：并查集

#include <bits/stdc++.h>
using namespace std;
#define N 100005
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    vector<int> fa(N), size(N);
    for (int i = 0; i < N; ++i) {
        fa[i] = i;
        size[i] = 1;
    }
    function<int(int)> find_set = [&](int x) { return x == fa[x] ? x : (fa[x] = find_set(fa[x])); };
    auto union_sets = [&](int x, int y) -> bool {
        x = find_set(x), y = find_set(y);
        if (x == y) {
            return false;
        }
        if (size[x] < size[y]) {
            swap(x, y);
        }
        fa[y] = x;
        size[x] += size[y];
        return true;
    };
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &x : a) {
        cin >> x;
    }
    for (int i = 0; i < n / 2; ++i) {
        if (a[i] != a[i + n / 2]) {
            union_sets(a[i], a[i + n / 2]);
        }
    }
    unordered_map<int, vector<int>> mp;
    for (int i = 0; i < N; ++i) {
        mp[find_set(i)].emplace_back(i);
    }
    int ans = 0;
    for (auto it = mp.cbegin(); it != mp.cend(); ++it) {
        ans += it->second.size() - 1;
    }
    cout << ans << '\n';
    return 0;
}

第五题：二叉树中序遍历，直接模拟交换

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, m, k, l, r, x;
    cin >> n >> m >> k;
    vector<TreeNode *> nodes(n + 1);
    for (int i = 1; i <= n; ++i) {
        nodes[i] = new TreeNode(i);
    }
    nodes[0] = nullptr;
    for (int i = 1; i <= n; ++i) {
        cin >> l >> r;
        nodes[i]->left = nodes[l];
        nodes[i]->right = nodes[r];
    }
    while (m--) {
        cin >> x;
        swap(nodes[x]->left, nodes[x]->right);
    }
    vector<int> ans;
    function<void(TreeNode *)> Dfs = [&](TreeNode *root) {
        if (!root) {
            return;
        }
        Dfs(root->left);
        ans.emplace_back(root->val);
        Dfs(root->right);
    };
    Dfs(nodes[k]);
    for (int i = 0; i < n; ++i) {
        cout << ans[i] << " \n"[i == n - 1];
    }
    return 0;
}

#美团笔试##笔试题目##美团#