http://acm.hdu.edu.cn/showproblem.php?pid=3177

单独比较两个物品:设a1+b2为先放第一件物品,后放第二件物品的最大瞬时体积,a2+b1为先放第二件物品,后放第一件物品的最大瞬时体积,则我们应该选择a1+b2和a2+b1中比较小的先放,相同则不加处理。

相似题目:POJ 3045 Cow Acrobats

/*0ms,264KB*/

const int mx = 1005;

struct node
{
    int a, b;
    /// 单独比较两个物品:设a1+b2为先放第一件物品,后放第二件物品的最大瞬时体积,
 /// a2+b1为先放第二件物品,后放第一件物品的最大瞬时体积,
 /// 则我们应该选择a1+b2和a2+b1中比较小的先放,相同则不加处理。
 bool operator < (const node &n) const
    {
        return a + n.b < n.a + b;
    }
} equip[mx];

int main()
{
    int t, v, n, i;
    SI(t);
    while (t--)
    {
        SII(v, n);
        For(i, n) SII(equip[i].a, equip[i].b);
        sort(equip, equip + n);
        For(i, n)
        {
            if (equip[i].b > v) break;
            v -= equip[i].a;
        }
        puts(i == n ? "Yes" : "No");
    }
    return 0;
}

Comments

comments powered by Disqus