运算符重载排序结构体TOJ1469

1.jpg 2.jpg
题目解析：
对n个木桩按双标准排序（先满足长度，再满足重量），之后贪心策略为每次找出一组木桩，使组内满足且，这样组内换木桩就不需要重新安装，剩下的木桩再进行寻找，直到所有木桩都属于某个组。
代码:

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

class Node{
    public:
    int x,y;
    Node(){}
    bool operator < (const Node n) const{//重载<，便于排序
      if(x==n.x) return y< n.y;
        return x < n.x;
    }
};

Node node[5005];
int cases,n,flag[5005];

int main()
{
    cin>>cases;//输入样例数
    while(cases--){
        cin>>n;//输入木桩数
        for (int i = 0; i < n;i++)
            cin>>node[i].x>>node[i].y;//每个木桩的长度与重量
        sort(node, node + n);//升序排序
        memset(flag, 0, sizeof(flag));//表示某个木桩是否属于某个组，0表示没有
        int ans = 0;
        for (int i = 0; i < n;i++){
            if (flag[i] == 0){//该木桩暂时不属于某个组
                int p =node[i].y;
                for (int j = i; j < n;j++){//尽量找到更多的可以归为同一组的木桩
                    if(flag[j]==0&&node[j].y >=p){
                        p = node[j].y;
                        flag[j] = 1;
                    }
                }
                ans++;//找到一个新的组，总时间增加
            }
        }
        cout << ans << endl; //输出结果
    }
    system("pause");
    return 0;
}

其中，重载"<"的代码对于双标准排序起了重要作用，这是菜鸡第一次明白运算符重载是如此使用的。

 bool operator < (const Node n) const{//重载<，便于排序
      if(x==n.x) return y< n.y;
        return x < n.x;
    }

记下一篇博客网址以供日后学习：
https://www.runoob.com/cplusplus/cpp-overloading.html