ZCMU-1373-Crixalis's Equipment

admin管理员组

文章数量:1531767

1373: Crixalis's Equipment

Time Limit: 1 Sec   Memory Limit: 128 MB
Submit: 49   Solved: 15
[ Submit][ Status][ Web Board]

Description

Crixalis - Sand King used to be a giant scorpion(蝎子) in the deserts of Kalimdor. Though he's a guardian of Lich King now, he keeps the living habit of a scorpion like living underground and digging holes.

Someday Crixalis decides to move to another nice place and build a new house for himself (Actually it's just a new hole). As he collected a lot of equipment, he needs to dig a hole beside his new house to store them. This hole has a volume of V units, and Crixalis has N equipment, each of them needs Ai units of space. When dragging his equipment into the hole, Crixalis finds that he needs more space to ensure everything is placed well. Actually, the ith equipment needs Bi units of space during the moving. More precisely Crixalis can not move equipment into the hole unless there are Bi units of space left. After it moved in, the volume of the hole will decrease by Ai. Crixalis wonders if he can move all his equipment into the new hole and he turns to you for help.

Input

The first line contains an integer T, indicating the number of test cases. Then follows T cases, each one contains N + 1 lines. The first line contains 2 integers: V, volume of a hole and N, number of equipment respectively. The next N lines contain N pairs of integers: Ai and Bi.
0<T<= 10, 0<V<10000, 0<N<1000, 0 <Ai< V, Ai <= Bi < 1000.

Output

For each case output "Yes" if Crixalis can move all his equipment into the new hole or else output "No".

Sample Input

2 20 3 10 20 3 10 1 7 10  2 1 10 2 11

Sample Output

Yes No
【解析】 这道题的话就是差不多蝎子搬东西搬到洞里面，首先输入t组数据，然后给出这个洞的容量，然后给出两个体积，一个是实际占用的体积，一个是移动需要的体积，题目的要求是问能不能全部搬进去，如果可以输出Yes,否则输出No,那这个时候我们就想啊，怎么样可以让东西快点搬进去，其实这个时候我们可能会想到让移动体积大的先搬进去，这个想法是没错不过也是片面的，如果说移动起来的体积大的，但是实际占用的体积也是比较大的呢，所以这个时候我们就想到用差值，这两个体积的差值大的先进去，为什么这么说，因为你想啊，两个体积差值大，是前面小，后面大，就是说后面移动的体积如果不是很大的话那也没事因为他们的差值大所以占用的体积一定小，如果说前面的体积没那么小也没关系，因为后面的移动的体积大，最开始先移动它肯定能把它移走。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct E
{
    int x;
    int y;
    int cha;
};
bool cmp(E a,E b)
{
    return a.cha>b.cha;
}
int main()
{
    int t,n,m,k,i,flag;
    scanf("%d",&t);
    while(t--)
    {
        E a[1001];
        flag=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d",&a[i].x,&a[i].y);
            a[i].cha=a[i].y-a[i].x;
        }
        sort(a,a+m,cmp);
        for(i=0;i<m;i++)
        {
            if(n>=a[i].y)
            {
                n-=a[i].x;
            }
            else
            {
                flag=1;
                break;
            }
        }
        if(flag==1)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}

本文标签： ZCMUequipmentCrixalis