潍坊一中 2023 秋提高级友好学校赛前联测 1

AisDaeun 11 2023-10-29

称霸

考虑转化为判定,利用二分求解。

#include <bits/stdc++.h>
int read() {
	int x = 0; bool fl(0); char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) fl = ch == '-';
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	return fl ? -x : x;
}
const int N = 1e6 + 10;
int d[N], a[N], n, m;
std::bitset<N> v, p;
bool check(int t) {
	v.reset(), p.reset();
	for (int i = t; i >= 1; i--) {
		if (!v[d[i]]) v[d[i]] = true, p[i] = d[i];
		else p[i] = false;
	}
	int c = 0;
	for (int i = 1; i <= t; i++) {
		if (p[i]) c -= a[d[i]]; else c++;
		if (c < 0) return false;
	}
	return (int)p.count() == m;
}
signed main() {
	std::ios::sync_with_stdio(false);
	n = read(), m = read();
	for (int i = 1; i <= n; ++i) d[i] = read();
	for (int i = 1; i <= m; ++i) a[i] = read();
	int l = 1, r = n + 1;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid; else l = mid + 1;
	}
	if (l == n + 1) l = -1;
	std::cout << l << '\n';
	return 0;
}

K

Mystia 的居酒屋

代码修改