UVa11729-贪心算法

题目链接：点击这里

此题可用简单的贪心算法，具体可见CLRS中的贪心算法介绍。
可使用Exchange策略进行证明：当对执行任务进行递减排序并且依次执行时，可以达到最优解。
解题的基本思路：首先利用结构体存储每个部下的交代任务和执行任务的时间，然后进行操作符重载，使得可以直接使用内置sort函数进行排序，然后就能很愉快的AC了。
注意：进行操作符重载时只能重载<号。
问题：书上的标准代码，对结构体进行新建对象时采用的(work){b,j}，不太理解。。。
算法复杂度为 O(nlgn)。
C++代码如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct work
{
    int b,j;
    bool operator < (const work& x)const
    {
        return j > x.j;   //在这里操作符只能重载<号，因此return为>即可实现递减序列排序
    }
    work(int x, int y)
    {
        b = x;
        j = y;
    }
};

int main()
{
    int n,b,j,CASE = 1;
    while(cin>>n && n)
    {
        vector<work> temp;
        for(int i = 0; i < n; i++)
        {
            cin>>b>>j;
            temp.push_back(work(b,j));//(work){b,j}
        }
        sort(temp.begin(),temp.end());
        int worktime = 0;
        int ans = 0;
        for (int i = 0; i < n; i++)
        {
            worktime += temp[i].b;
            ans = max(ans,worktime+temp[i].j);
        }
        cout<<"Case "<<CASE++<<": "<<ans<<endl;
    }
    return 0;
}

·