提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其它

当前栏目

HDU 3177 Crixalis's Equipment （贪心，差值）

&# 39 HDU 贪心 差值
2023-09-11 14:17:19 时间

题意：判断 n 件物品是否可以搬进洞里，每件物品有实际体积A和移动时的额外体积 B 。

析：第一反应就是贪心，一想是不是按B从大到小，然后一想，不对，比如体积是20，第一个

是A=11， B=19.第二个是A = 1，B = 18.很明显不对。

我们取AB的差值，进行贪心，为什么呢？

我反过来想一下，假设我们把两个物品搬到洞中，所需要的洞的最小体积。第一个，A = 2，B = 10.

第二个，A = 5， B = 10.如果先放第一个，第放第二个，体积为12，如果反过来则是15，很明显是先放

差值大的，这样为下一个放留下较大的空间。

代码如下：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <map>
#include <cctype>

using namespace std;
const int maxn = 1000 + 5;
struct node{
    int A, B;
    bool operator < (const node &p) const {
        return (B - A) > (p.B - p.A);
    }
};
node a[maxn];

int main(){
//    freopen("in.txt", "r", stdin);
    int T, n, v; cin >> T;
    while(T--){
        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);

        bool ok = true;
        for(int i = 0; i < n; ++i){
            if(v < a[i].B){ ok = false;  break; }
            v -= a[i].A;
        }
        
        if(ok)   puts("Yes");
        else puts("No");
    }
    return 0;
}

 

相关文章