Applejack and Storages

题目链接: Applejack and Storages

大致题意:

初始给你n个长度为a[i]的木板, 有q次操作, 会进行添加或者减少木板, 问你在每次操作后能否用已有的木板搭建出一个正方形和一个长方形(长方形也可以是正方形). 其中木板不可以拼接, 保证不会移除不存在的木板.

解题思路:

如果要能满足条件, 我们需要有一组4个长度相同的木板, 还要有两组2个长度相同的木板, 或者两组4个长度相同的木板. 我们可以发现, 4个相同长度的木板是优先级最高的, 对于同一个长度x, 如果能凑出4个, 一定比凑两组2个要好. 所以不妨我们设立两个集合, 一个集合装有4个长度相同的木板, 另外一个集合装有2个长度相同的木板.

AC代码:

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1e5 + 10;
int a[N]; //当前长度为i的木板数量
multiset<int> st1; //4个
set<int> st2; //2个
void fact(int x) {
	if (a[x] >= 2) { //要放入集合
		a[x] -= 2;
		if (st2.count(x)) st2.erase(x), st1.insert(x); //集合2中已经存在, 表明此时有4个, 放入集合1
		else st2.insert(x);
	}
	else if (a[x] < 0) { //减少了木板
		if (st2.count(x)) a[x] = 1, st2.erase(x); //能从集合2取则从集合2取
		else {
			auto index = st1.find(x); st1.erase(index);
			st2.insert(x);
			a[x] = 1;
		}
	}
}
int main(void)
{
	int n; cin >> n;
	for (int i = 1; i <= n; ++i) {
		int x; scanf("%d", &x);
		a[x]++; fact(x);
	}
	int m; cin >> m;
	char op[2]; int x;
	while (m--) {
		scanf("%s%d", op, &x);
		if (op[0] == '+') a[x]++;
		else a[x]--;
		fact(x);
		if (st1.size() >= 2 || st1.size() >= 1 && st2.size() >= 2) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

END