HD-ACM算法专攻系列（23）—

题目描述：

AC源码：
此次考察贪心算法，解题思路：贪心的原则是使留下的空间最大，优先选择Bi与Ai差值最大的，至于为什么？这里用只有2个设备为例，（A1,B1）与（A2,B2），假设先搬运A1，搬运的那一瞬间，实际将要占用的空间应该为A1+B2，那么为了保证留下的空间最大，则应该有A1+B2<A2+B1成立，才能先搬运A1，即B1-A1>B2-B1。（n个设备可以两两做这样的比较，来达到选择的最优）

#include"iostream"

#include"algorithm"

using namespace std;

struct Equipment

{

    int A;

    int B;

};

bool cmp(Equipment a, Equipment b)

{

    return (a.B - a.A) > (b.B - b.A);

}

int main()

{

    int t, v, n;

    bool flag;

    Equipment eq[1000];

    scanf("%d", &t);

    for(int i = 0; i < t; i++)

    {

            scanf("%d %d", &v, &n);

            for(int j = 0; j < n; j++)

            {

                scanf("%d %d", &eq[j].A, &eq[j].B);

            }

            sort(eq, eq+n, cmp);

            flag = true;

            for(int j = 0; j < n; j++)

            {

                if(eq[j].B <= v)

                {

                    v -= eq[j].A;

                }

                else

                {

                    flag = false;

                    break;

                }

            }

            if(flag)

            {

                printf("Yes\n");

            }

            else

            {

                printf("No\n");

            }

    }

    return 0;

}

巴特西

HD-ACM算法专攻系列（23）——Crixalis's Equipment

最新文章

热门文章