1 条题解
-
0
妙妙题。
考虑贪心。
如果直接贪心放每一个东西,会非常复杂和容易错,考虑简单的做法。
如果一个人的载重量是 ,给他一个重量为 的货物,那么相当于多了一个载重量为 的人。
考虑从大到小分配货物。
显然只能给 的人拿。
先给 的人,再考虑给 的人。
证明
考虑有两个人,载重量分别为 $4,5$,我有一个重量为 $4$ 的货物需要分配。如果给 , 还剩 的空间, 还剩 的空间。
如果给 , 还剩 的空间, 还剩 的空间。
显然,一整块的 比分开的 更为优秀,比如 可以放下 ,而 不行。
同理, 需要先给 ,然后考虑先给 ,再给 。
证明
现在来考虑 $3$ 先给 $5$ 更优的问题。由于现在放 必须放完,相当于考虑剩余空间对放 的贡献。
如果将 给了 那么接下来这个人只能拿 。
如果将 给了 那么接下来这个人既可以拿 也可以拿 。
所以先把 给 更优。
最后剩下 ,先把 乱放放完,然后再随便放 就好了。
#include<bits/stdc++.h> using namespace std; typedef long long ll; int _; ll a[6],b[6]; void work(int x,int y){//把重量为 x 的东西贪心地给 y 拿 ll p=min(a[x],b[y]); a[x]-=p;b[y]-=p; if(y-x)b[y-x]+=p; } int main() { scanf("%d",&_); while(_--){ for(int i=1;i<=5;i++)scanf("%lld",&a[i]); for(int i=1;i<=5;i++)scanf("%lld",&b[i]); work(5,5); work(4,4),work(4,5); work(3,3),work(3,5),work(3,4); work(2,5),work(2,4),work(2,3),work(2,2); work(1,5),work(1,4),work(1,3),work(1,2),work(1,1); int ff=0; for(int i=1;i<=5;i++)if(a[i])ff=1; puts(ff?"No":"Yes"); } return 0; }
- 1
信息
- ID
- 50
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者