首页 > 其他 > 详细

hdu acm-step 1.3.8 Crixalis's Equipment

时间:2017-08-19 21:00:32      阅读:312      评论:0      收藏:0      [点我收藏+]

技术分享

    本题题意:蝎子王搬家,洞的空间是V,共有N件物品要搬,每件物品在搬运过程中要占用Bi空间,搬运完后占用Ai,问蝎子王能否搬完所有的物品。

    代码如下:

#include <cstdio>
#include <algorithm>
using namespace std;
struct Node
{
        int A,B;
        bool operator < (const Node &node){if(B-A>node.B-node.A)return true;else if(B - A< node.B - node.A)return false;if(A < node.A)return true;return false;}
};
Node a[1000];
int main()
{
        int T;
        scanf("%d",&T);
        while(T--)
        {
                int V,N;
                scanf("%d%d",&V,&N);
                for(int i=0;i<N;i++)scanf("%d%d",&a[i].A,&a[i].B);
                sort(a,a+N);
                int sum=0,i;
                for(i=0;i<N;i++){if(a[i].B > V-sum)break;sum+=a[i].A;}
                if(i!=N||sum>V)printf("No\n");
                else printf("Yes\n");
        }
        return 0;
}

这道题真的是很难想清楚,后来查了题解才做出来,说是贪心B-A,B-A的含义是需要的预留空间,预留空间大的优先,然后相同情况下取实际空间更小的,可以为后来留更大的空间。

hdu acm-step 1.3.8 Crixalis's Equipment

原文:http://www.cnblogs.com/mtl6906/p/7397683.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!