TOJ-1469-Wooden Sticks(贪心)

题意：

有许多木桩需要处理，每个木桩有一个长度Li和重量Wi，给机器安装第一个木桩需要1分钟，之后每次换木桩时，若新木桩的长度Li'<=Li,重量Wi'<=Wi,则不需耗时；否则，重新安装，耗时一分钟，给出t组数据，每组有n个木桩，分别给出长度和重量，求每组木桩最小安装时间。

思路：

最小解问题，贪心，升序排序后，对木桩进行分组即可

代码：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iomanip>
#include<algorithm>
#include<string.h>

using namespace std;
const int maxn=5100;
typedef long long ll;

class node
{
public:
  int x,y;
  node(){}
  bool operator < (const node &n){
    if(x==n.x) return y<n.y;
    return x<n.x;
  } 
};

node a[maxn];
int flag[maxn];
int t,n;
int main()
{
  cin>>t;
  while(t--)
  {
    cin>>n;
    for(int i=0; i<n; i++)
     cin>>a[i].x>>a[i].y;
    sort(a,a+n);
    memset(flag,0,sizeof(flag));
    int ans=0;
    for(int i=0; i<n; i++)
    {
      if(!flag[i])
      {
        int p=a[i].y;
        for(int j=i; j<n; j++)
        {
          if(!flag[j]&&a[j].y>=p)
          {
            p=a[j].y;
            flag[j]=1;
          }
        }
        ans++;
      }
    }
    cout<<ans<<endl;
  }
  system("pause");
  return 0;
}