360提前批笔试

一.选择题

基本不会做，好几个数学题加机器学习。

二.编程题

第一题：给你一个长度为50000的序列，你每次可以把一个数值的所有位置的数+一个v（v可以为正负），问你最少操作几次可以把这个序列变成相等的。

第二题：给你一个长度为100000的序列，再给你一个长度为k的操作序列，记每一次操作数为vi，每次都会当前这个序列小于vi的数放左边，大于的放右边，注意相对顺序是不能变的。

这个题考虑，小的数先排一定不会影响大的，因此我们考虑离线做，对操作数从小到大排序，对于每一个操作数，我们先把小于他的数按相对顺序放，然后再考虑放他自己，操作完成后那些没有被移动的数按相对顺序放即可。复杂度为O(nlogn)

#include "bits/stdc++.h"
using namespace std;
using pii = pair<int, int>;
int main() {
	int n, m;
	cin >> n;
	vector<int> a(n), c(n);
	map<int, deque<int>> mp;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
		mp[a[i]].push_back(i);
	}
	cin >> m;
	vector<int> b(m);
	for (int i = 0; i < m; i++) {
		cin >> b[i];
	}
	sort(b.begin(), b.end());

	vector<int> na;
	for (int i = 0; i < m; i++) {
		vector<int> val;
		if (mp.size()) {
			auto it = mp.begin();
			while (it != mp.end() && it->first < b[i]) {
				val.push_back(it->first);
				it = next(it);
			}
		}
		priority_queue<pii, vector<pii>, greater<pii>> Q;
		for (auto &p : val) {
			Q.push({mp[p].front(), p});
			mp[p].pop_front();
		}
		while (!Q.empty()) {
			auto [p, v] = Q.top();
			Q.pop();
			c[p] = true;
			na.push_back(v);
			if (!mp[v].size()) {
				mp.erase(v);
			} else {
				Q.push({mp[v].front(), v});
				mp[v].pop_front();
			}
		}
		if (mp.count(b[i])) {
			for (auto &p : mp[b[i]]) {
				c[p] = true;
				na.push_back(b[i]);
			}
			mp.erase(b[i]);
		}
	}
	for (int i = 0; i < n; i++) {
		if (!c[i]) {
			na.push_back(a[i]);
		}
	}
	a.swap(na);
	for (int i = 0; i < n; i++) {
		cout << a[i] << ' ';
	}
	return 0;
}