有五种种类的垃圾,数量分别为 \(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;
}
- ICPC Southern Regional Contest Russianicpc southern regional contest acm-icpc regional contest nanjing regional contest 2022 icpc acm-icpc regional contest seoul programming acm-icpc american regional the universal acm-icpc regional regional contest macau 2021 regional central contest europe programming shenyang regional contest regional contest nanjing 2022