寒武纪 9.19笔试题C++题解

第一题

分数的上取整

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int fun(int x) {
    if (x < 38) return x;
    int y = x;
    while (y % 5 != 0) y++;
    if ((y - x) < 3) return y;
    return x;
}

int main() {
    //
    ll n;
    cin >> n;
    int x;
    while (n--) {
        cin >> x;
        cout << fun(x) << endl;
    }
    return 0;
}

第二题

区间修改，单点查询，用查分数组做

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int n, m; // 列表长度为N，M个操作
void fun(ll diff[], int a, int b, int k) {
    // a b之间的元素增加k
    diff[a] += k;
    diff[b + 1] -= k;
}
void cal(ll arr[], ll diff[]) {
    for (int i = 1; i <= n; i++) { arr[i] = arr[i - 1] + diff[i]; }
}
#define show(x, idx, n)                                                                                                                                        \
    for (int i = idx; i < n; i++) cout << x[i] << ' ';                                                                                                         \
    cout << endl;

int main() {
    //
    cin >> n >> m;
    ll arr[n + 1];
    ll diff[n + 2]; // 差分数组
    // diff[1] = arr[1]-arr[0];
    // arr[1] = arr[0]+diff[1];
    memset(arr, 0, sizeof(arr));
    memset(diff, 0, sizeof(diff));
    int a, b, k;
    while (m--) {
        cin >> a >> b >> k;
        fun(diff, a, b, k);
        // cal(arr, diff);
        // show(arr, 1, n + 1);
    }
    cal(arr, diff);
    // int res = max_element(arr+1, arr+n+1);
    ll res = arr[1];
    // show(arr, 1, n + 1);
    for (int i = 2; i <= n; i++) { res = max(res, arr[i]); }
    cout << res;

    return 0;
}

第三题

pop出数组里最小的两个数a,b push进 a+2b

用最小堆做，这里有一个坑

当最后只有一个数，找不到第二小的数，不能使得所有数都大于k时，输出-1

题目里没有讲，自己试出来的，没有考虑到这条只能过55.56%

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main() {
    //
    ll k;
    int n;
    cin >> n >> k;
    ll t;
    priority_queue<ll, vector<ll>, greater<ll>> q;
    for (int i = 0; i < n; i++) {
        cin >> t;
        q.emplace(t);
    }
    int res = 0;
    while (!q.empty() && q.top() < k) {
        res++;
        ll x = q.top();
        q.pop();
        ll y;
        if (q.empty()) {
            y = x;
        } else {
            y = q.top();
            q.pop();
        }
        ll z = x + 2 * y;

        q.emplace(z);
    }
    cout << res;

    return 0;
}

第四题

求至少交换多少次使得数组有序，一开始只想到升序，过了60%，其实降序也可以。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define show(x, idx, n)                                                                                                                                        \
    for (int i = idx; i < n; i++) cout << x[i] << ' ';                                                                                                         \
    cout << endl;
int res = 0;
int n;
void fun(vector<int> &arr, int idx, int x) {
    // 当前的索引是idx，它的值是x
    // 如果idx==x 直接结束
    if (idx == x) return;
    res++;
    // 否则, 把x调整到x的位置
    swap(arr[idx], arr[x]);
    // 此时arr[idx]被调整到了合适的位置
    // 但是当前位置idx又不对了
    // show(arr, 0, n);
    fun(arr, idx, arr[idx]);
}
int main() {
    //
    cin >> n;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) { cin >> arr[i]; }
    vector<int> arr2(arr);
    vector<int> arr3(arr);
    sort(arr2.begin(), arr2.end());
    unordered_map<int, queue<int>> mp(n);
    for (int i = 0; i < n; i++) { mp[arr2[i]].emplace(i); }
    for (int i = 0; i < n; i++) {
        int x = arr[i];
        arr[i] = mp[x].front();
        mp[x].pop();
    }
    // show(arr2, 0, n);
    // show(arr, 0, n);
    for (int i = 0; i < n; i++) { fun(arr, i, arr[i]); }
    int ans = res;
    // cout << res;
    // cout << endl;

    sort(arr2.begin(), arr2.end(), greater<int>());
    unordered_map<int, queue<int>> mp1(n);

    for (int i = 0; i < n; i++) { mp1[arr2[i]].emplace(i); }
    for (int i = 0; i < n; i++) {
        int x = arr3[i];
        arr3[i] = mp1[x].front();
        mp1[x].pop();
    }
    // cout << res;
    // show(arr2, 0, n);
    // show(arr3, 0, n);
    res = 0;
    for (int i = 0; i < n; i++) { fun(arr3, i, arr3[i]); }
    // cout << res;
    // cout << endl;
    cout << min(ans, res);

    return 0;
}