寒武纪 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;
} 
