1 条题解

  • 0
    @ 2021-11-19 9:55:41

    妙妙题。

    考虑贪心。

    如果直接贪心放每一个东西,会非常复杂和容易错,考虑简单的做法。

    如果一个人的载重量是 xx,给他一个重量为 yy 的货物,那么相当于多了一个载重量为 xyx-y 的人。

    考虑从大到小分配货物。

    55 显然只能给 55 的人拿。

    44 先给 44 的人,再考虑给 55 的人。

    证明 考虑有两个人,载重量分别为 $4,5$,我有一个重量为 $4$ 的货物需要分配。

    如果给 5555 还剩 11 的空间,44 还剩 44 的空间。

    如果给 4455 还剩 55 的空间,44 还剩 00 的空间。

    显然,一整块的 55 比分开的 1,41,4 更为优秀,比如 55 可以放下 2,32,3,而 1,41,4 不行。

    同理,33 需要先给 33,然后考虑先给 55,再给 44

    证明 现在来考虑 $3$ 先给 $5$ 更优的问题。

    由于现在放 33 必须放完,相当于考虑剩余空间对放 1,21,2 的贡献。

    如果将 33 给了 44 那么接下来这个人只能拿 11

    如果将 33 给了 55 那么接下来这个人既可以拿 22 也可以拿 11

    所以先把 3355 更优。

    最后剩下 1,21,2,先把 22 乱放放完,然后再随便放 11 就好了。

    #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
    上传者