美团笔试（22.03.19）

代码题

一共五道代码题，看了前面三道，ac了三道，后面两道题没有时间看，此处将对前三题进行记录总结，后附代码。

第一题 点餐

题意：
给定一组n个商品的价格，下单购买商品时，必须购买前i个商品，即购买商品列表是商品列表的前缀。提供两种优惠规则，满减优惠和折扣优惠，每次下单只能选择某种优惠规则。问购买前i（1<=i<=n）个商品时，使用哪种优惠策略较优，或者两者一样优。

• 满减规则：给定若干满减优惠券，如10-5,20-10等，实际付款等于商品原价总和减去满减优惠券优惠价格。
• 折扣规则：每个商品提供一个折扣价，实际付款为所有商品的折扣价之和。

临场解题思路：
购买前i个商品时，计算商品原价格、商品折扣价格、商品满减价格。那种策略优惠选择哪种规则。

• 商品原价格直接累加，使用前缀和
• 商品折扣价格直接累加，使用前缀和
• 商品满减价格等于商品原价格总和减去最近额度的满减优惠券优惠价格，使用二分法搜索最近可用满减优惠券

题目争议：
购买20元商品，有10-5和15-1两张优惠券，题目要求使用15-1的优惠券，过于离谱。（题目没有说明，根据测试结果倒推的题意）

反思：
满减优惠券是按满额从小到大排序的，商品价格的前缀和也是按从小达到排序的。遍历商品价格前缀和数组时，随着付款总额越来越大，使用的优惠券满额也会越来越大。针对这一点，遍历前缀和数组的某个元素的时候，可以使用一个变量记录当前使用的优惠券下标，处理下一个前缀和元素时，优惠券下标必然大于等于上一次使用的优惠券的下标。

第二题 加密解密

题意：
给定字符串s，可以选择对字符串进行加密或者解密。加密时，每次取原字符串中间元素，加入加密字符串的尾部，然后删除中间的元素，重复着这一过程，知道原字符串为空。解密时，按加密过程对加密字符串反向操作还原出原始字符串。
临场解题思路：
加密：模拟加密字符串过程，发现加密过程可以概括为从原始字符串中间，使用两个指针（left与right）分别向左与向右遍历，左右交替遍历元素并加入加密字符串。
解密：反向操作，反向遍历加密字串符，交替选择字符加入前缀字符串和后缀字符串，然后将前缀字符串和后缀字符串拼接为原始字符串。

第三题 文件版本冲突

题意：
给定n个文件，需要在两台电脑之间同步。若用户在A、B电脑上都修改了某些文件，同步软件会提示冲突。用户现在A电脑上进行了修改，然后在B电脑上修改文件，问有多少文件修改出现冲突。用户每次修改会影响多个连续文件，使用一个编号区间表示[l,r]，题目给定A电脑上的m1个修改操作，与B电脑上的m2个修改操作。
临场思路：
计算A电脑与B电脑修改文件的重叠区间部分文件个数。需要注意的是，A电脑上的多个修改区间会重叠，在计算A与B之间重叠文件时，可能会引入对同一文件重复计算的情况，需要对统一电脑的修改区间进行重叠区间的合并操作。

• 同一电脑上上区间的排序与合并，同一台电脑上的多个修改操作影响的文件编号区间可能出现重叠的情况，需要合并重叠的区间。
• A、B电脑之间区间重叠部分文件个数的计算，使用两个指针pa，pb变量A与B的修改区间序列，累加重叠部分文件数。

反思：
可以基于集合计算，直接将A电脑修改的文件编号放入集合中。然后遍历B电脑修改的文件编号，通过查询集合是否出现该编号，即可判断是否出现冲突，若冲突，累加冲突计数。该方法优点在于实现简单，缺点在于使用更多的内存空间，每个文件编号使用一个整数存储，对于区间表示法，可以通过两个整数表示若干文件。

反思

• 笔试前一晚入睡较晚，早上起床精神状态不是很好，头脑不清晰
• 进20天没有刷题，手感生疏了，写代码较慢，后序需要通过刷题保持手感
• 近一两年刷题基本使用提供核心代码模式的leetcode平台,长久没有使用ACM刷题模式刷题，处理输入输出有点生疏了
• 第一次听说并使用赛码网code答题，下次笔试前需要注意提前熟悉code平台

代码

第一题 点外卖

#include <bits/stdc++.h>

using namespace std;

int m, n;
vector<int> pay, pay_z, pay_m;
vector<int> rule_c, rule_d;

void input();
int findRule(int val);
int main() {
	input();

	for (int i = 1; i < n; i++) {
		pay[i] += pay[i - 1];
	}
	for (int i = 1; i < n; i++) {
		pay_z[i] += pay_z[i - 1];
	}
	for (int i = 0; i < n; i++) {
		int rule_idx = findRule(pay[i]) - 1;
		if (rule_idx >= 0)
			pay_m[i] = pay[i] - rule_d[rule_idx];
		else
			pay_m[i] = pay[i];
	}

	string res;
	for (int i = 0; i < n; i++) {
		if (pay_z[i] == pay_m[i]) {
			res.push_back("B");
		} else if (pay_z[i] < pay_m[i]) {
			res.push_back("Z");
		} else {
			res.push_back("M");
		}
	}
	cout << res;

	return 0;
}


int findRule(int val) {
	int left = 0, right = m;
	while (left < right) {
		int middle = (left + right) / 2;
		if (rule_c[middle] <= val)
			left = middle + 1;
		else
			right = middle;
	}
	return left;
}

void input() {
	cin >> n;
	pay.resize(n);
	pay_z.resize(n);
	pay_m.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> pay[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> pay_z[i];
	}

	cin >> m;
	rule_c.resize(m);
	rule_d.resize(m);
	for (int i = 0; i < m; i++) {
		cin >> rule_c[i];
	}
	for (int i = 0; i < m; i++) {
		cin >> rule_d[i];
	}
}

第二题代码 加密解密

#include <bits/stdc++.h>

using namespace std;

int n, op;
string is, os;
string pre_str, back_str;


void op_one();
void op_two();
int main() {
	cin >> n >> op;
	cin >> is;

	if (op == 1) {
		op_one();
	} else {
		op_two();
	}
	cout << os;
	return 0;
}

void op_one() {
	int left, right;
	left = (n + 1) / 2 - 1;
	right = left + 1;
	if (n % 2 == 1) {
		os.push_back(is[left--]);
	}

	while (left >= 0) {
		os.push_back(is[left--]);
		os.push_back(is[right++]);
	}
}

void op_two() {
	int i = n;

	if (n % 2 == 1) {
		back_str.push_back(is[--i]);
		for (; i >= 2; i -= 2) {
			pre_str.push_back(is[i - 1]);
			back_str.push_back(is[i - 2]);
		}
	} else {
		for (; i >= 2; i -= 2) {
			back_str.push_back(is[i - 1]);
			pre_str.push_back(is[i - 2]);
		}
	}
	reverse(back_str.begin(), back_str.end());
	os = pre_str + back_str;
}

第三题 文件同步冲突

#include <bits/stdc++.h>

using namespace std;

int n, m1, m2;
vector<vector<int>> modi1, modi2;

void input();

int main() {
	input();
	int ans = 0;
	int i = 0, j = 0;
	while (i < modi1.size() && j < modi2.size()) {
		if (modi1[i][1] < modi2[j][0]) {
			i++;
		} else if (modi1[i][0] > modi2[j][1]) {
			j++;
		} else {
			ans += min(modi1[i][1], modi2[j][1]) - max(modi1[i][0], modi2[j][0]) + 1;
			if (modi1[i][1] < modi2[j][1])
				i++;
			else
				j++;
		}
	}
	cout << ans;

	return 0;
}

void input() {
	cin >> n >> m1 >> m2;

	modi1.resize(m1, vector<int>(2));
	modi2.resize(m2, vector<int>(2));
	for (int i = 0; i < m1; i++) {
		cin >> modi1[i][0];
	}
	for (int i = 0; i < m1; i++) {
		cin >> modi1[i][1];
	}
	for (int i = 0; i < m2; i++) {
		cin >> modi2[i][0];
	}
	for (int i = 0; i < m2; i++) {
		cin >> modi2[i][1];
	}

	int idx1 = 1;
	sort(modi1.begin(), modi1.end());
	for (int i = 1; i < m1; i++) {
		if (modi1[i][0] <= modi1[idx1 - 1][1]) {
			modi1[idx1 - 1][1] = max(modi1[idx1 - 1][1], modi1[i][1]);
		} else {
			modi1[idx1++] = modi1[i];
		}
	}
	modi1.resize(idx1);

	int idx2 = 1;
	sort(modi2.begin(), modi2.end());
	for (int i = 1; i < m2; i++) {
		if (modi2[i][0] <= modi2[idx2 - 1][1]) {
			modi2[idx2 - 1][1] = max(modi2[idx2 - 1][1], modi2[i][1]);
		} else {
			modi2[idx2++] = modi2[i];
		}
	}
	modi2.resize(idx2);
}