526互联

2020-2021 ICPC, NERC, Southern and Volga Russian Regional Contest (Online Mirror, ICPC Rules) N. Waste Sorting

发布时间 2023-10-12 17:08:34作者: zsxuan

有五种种类的垃圾，数量分别为 \(a_1, a_2, a_3, a_4, a_5\) 。

  • 第一种为纸质垃圾
  • 第二种为塑料垃圾
  • 第三种双非垃圾
  • 第四种基本纸质垃圾
  • 第五种基本塑料垃圾

有三种垃圾桶，容量分别为 \(c_1, c_2, c_3\) 。

  • 第一种垃圾桶可以放入：纸质垃圾和基本纸质垃圾
  • 第二种垃圾桶可以放入：塑料垃圾和基本塑料垃圾
  • 第三种垃圾桶可以放入：双非垃圾、基本纸质垃圾、基本塑料垃圾

给出 \(a_{1 \sim 5}, c_{1 \sim 3}\) 。询问能否将所有垃圾扔入垃圾桶。

考虑从限制强的到限制弱的逐步解决。

先将第 \(1, 2, 3\) 种垃圾放入第 \(1, 2, 3\) 个垃圾桶。如果可以则继续，更新垃圾桶容量。

  • \(c_1 -= a_1, c_2 -= a_2, c_3 -= a_3\) 。

此时第 \(4\) 种垃圾可以装入第 \(1, 3\) 种垃圾箱；第 \(5\) 种垃圾可以装入第 \(2, 3\) 种垃圾箱。

于是先将限制强的不能共用的 \(1, 2\) 号垃圾箱装满，再将剩余的装入 \(3\) 号垃圾箱。

  • \(a_4 -= min(a_4, c_1), a_5 -= min(a_5, c_2)\)
  • \(a_4 + a_5 \leq c_3\)

上述原理仅在于：处理掉限制强的独立问题后，便可直接考虑不独立问题。

view 
#include <bits/stdc++.h>
void solve(){
	std::vector<int> a(5+1), c(3+1);
	for (int i = 1; i <= 3; i++) std::cin >> c[i];
	for (int i = 1; i <= 5; i++) std::cin >> a[i];
	if (a[1] <= c[1] && a[2] <= c[2] && a[3] <= c[3]) {
		c[1] -= a[1]; c[2] -= a[2]; c[3] -= a[3];
		a[4] -= std::min(a[4], c[1]); a[5] -= std::min(a[5], c[2]);
		if (a[4] + a[5] <= c[3]) std::cout << "YES\n";
		else std::cout << "NO\n";
	}
	else std::cout << "NO" << "\n";
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}