美团秋招第三场8.24笔试-Java后端

编程题（20 + 20 + 30）

（1）给定 二维平面上的起点和终点，再给定 n 个金币位置，需要从起点出发，将所有金币都带到终点，每次只能带一个金币，求最短路程。

做法：不考虑起点时，总花费为每个金币到终点距离*2， 然后再枚举第一个去的金币位置(总花费 + 起点到金币距离 - 终点到金币距离)，答案取min。

（2）给定三个数字a, b, c 和一个 k, 有 k 次操作将其中一个数字加上1，问a * b * c的最大值

做法：将abc尽量凑到相近就行了（每次给最小的数加），注意取模

（3）给定 n 个物品，每个物品有 0， 1两种类型以及价值，q 次询问 {l, r, t, k} 表示购买下标 [l, r] 内中类型为 t 的物品，其中价值最大的 k 个，输出购买的物品下标，不够时输出 -1。（操作之间是继承关系，非独立）

数据范围：1 <= n, q <= 1e5;

做法：题目给了两秒，一眼就是线段树板子了，但是还要维护区间不同种类物品最大值，比较麻烦，当时被第二题取模卡了太久，这题只剩20分钟写，也来不及码线段树，于是突然想到可以用并查集维护区间合并问题，常数还小，还好写。

具体来说，在执行购买操作时，假设要将第 i 个物品买掉， 那么可以将 i 的 father 指向 i + 1，也就是merge(i, i + 1)， 这样在遍历物品时，下一个还没被购买的物品就是 i + 1的father, 均摊几乎为 O(1) 复杂度。事实证明跑的很快

总复杂度：O(nlogn)

********更正一下***************

这题的查询如果全部是1~n区间查询，k = 1，那该复杂度会被卡成n^2logn, 事后想起来这题应该是随机数据被我卡过去了

上代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N], n, q, fa[N];

int f(int x) {
	while(fa[x] != x) x = fa[x] = fa[fa[x]];
	return fa[x];
}

void merge(int x, int y) {
	int fx = f(x), fy = f(y);
	fa[fx] = fa[fy]; 	
}

signed main() {
	cin >> n >> q;
	for(int i = 1; i <= n; i ++) cin >> a[i], fa[i] = i;
	for(int i = 1; i <= n; i ++) cin >> b[i];
	fa[n + 1] = n + 1;
	while(q --) {
		int l, r, t, k;
		cin >> l >> r >> t >> k;
		vector<pair<int, int>> p; 
		for(int i = l; i <= r; i = f(++ i)) {
			if(b[i] == t) {
				p.push_back({a[i], i});
			}
		}
		sort(begin(p), end(p), [&](pair<int, int> a, pair<int, int> b) -> bool {
			if(a.first != b.first)
				return a.first > b.first;
			return a.second < b.second;
		});
		for(int i = 0; i < k && i < p.size(); i ++) {
			cout << p[i].second << ' ';
			b[p[i].second] = -1;
			merge(p[i].second, p[i].second + 1);
		}
		if(k > p.size()) cout << -1;
		cout << endl;
	}
}

总结： 上次笔试考了线段树，这次压轴又来，还好想到了避开线段树的写法，不然时间也不够，第二题的数据范围给的很大，取模不知道哪里出了调了好久还是没满分

最后得分：100%、 65%、 100%