美团笔试(暑期转正岗) 2023.3.25

题目一

题目描述

给定两个序列a和b，序列长度为n，令a序列入栈，b序列为出栈顺序，判断合法性，共有10个test。

输入:
3
3
1 2 3
1 2 3

3
1 2 3
3 2 1

3
1 2 3
3 1 2

输出：
Yes
Yes
No

提示

1 <= n <= 50000

CPP (模拟）

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

const int N = 50010;

int a[N],b[N];
stack<int> s;
int main()
{
	int test;
	cin >> test;
	while (test -- ) {
		int n;
		cin >> n;
		while(s.size()) s.pop();
		for (int i = 0; i < n; i ++ ) cin >> a[i];
		for (int i = 0; i < n; i ++ ) cin >> b[i];
		int j = 0;
		for (int i = 0; i < n; i ++ ) {
			while (j < n && s.size() && b[j] == s.top()) {
				j ++;
				s.pop();
			}
			s.push(a[i]);
		}
		while (j < n && s.size() && b[j] == s.top()) {
			j ++;
			s.pop();
		}
		if (!s.size()) cout << "Yes" << endl; 
		else cout << "No" << endl;
	}
	return 0;
}

题目二

题目描述

给定两个序列a和b，长度分别为n和m。问每个b[i]能收取多少个a[i] * a[i]。

输入：
5 5
1 2 3 4 5
1 3 5 7 20

输出：
1 1 2 2 3

提示

1 <= n <= 50000
1 <= m <= 50000
1 <= a[i] <= 1e4
1 <= b[i] <= 1e18

CPP （排序+双指针）

#include <bits/stdc++.h>
using namespace std;
const int N = 50010;
int a[N];
pair<long long,int> q[N];
int res[N];
int main()
{
	int n,m;
	cin >> n >> m;
	for (int i = 0; i < n; i ++ ) cin >> a[i];
	for (int i = 0; i < m; i ++ ) {
		cin >> q[i].first;
		q[i].second = i;
	}
	sort(a,a + n);
	sort(q,q + m);
	int j = 0,cnt = 0;
	long long sum = 0;
	for (int i = 0; i < m; i ++ ) {
		while (j < n) {
			if (q[i].first >= sum + a[j] * a[j]) {
				sum += a[j] * a[j];
				cnt ++;
				j ++;
			} else break; 
		}
		res[q[i].second] = cnt;
	}
	for (int i = 0; i < m; i ++ ) cout << res[i] << " ";
	return 0;
}