题目描述
儿童节到了，幼儿园老师要给小朋友做一些手工创意巧克力，做法就是买了了一些普通条状巧克力进行加工。现有n块巧克力，知道它们的长度和重量。老师们需要用机器一根一根地加工这些巧克力。该机器在加工过程中需要一定的准备时间，是用于清洗机器，调整工具和模板的。需要的准备时间如下：
（1）第一根巧克力1min的准备时间；
（2）在加工了一根长为x，重为w的巧克力之后，接着加工一根长为xx（x<=xx），重为ww（w<=ww）的巧克力是不需要任何准备时间的。否则需要一分钟的准备时间。
老师们n条巧克力，你要找到最少的准备时间。例如现在有长和重分别为（4,9），（5,2），（2,1），（3,5）和（1,4）的五根巧克力，那么所需准备时间最少为2min，顺序为（1,4），（3,5），（4,9），（2,1），（5,2）。
输入
第一行是一个整数n（1<=n<=5000），表示有多少条巧克力；
第二行包括n*2个整数，表示了x1，w1，x2,w2......xn,wn，这些数均不大于10000，其中xi和wi表示第i巧克力的长度和重量。
输出
输出以分钟为单位的最少准备时间。
样例输入 Copy
5
4 9 5 2 2 1 3 5 1 4
样例输出 Copy
2
\
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
#define N 5000+10
struct node{
int l;
int w;
};
struct node num[N];
int cmp(struct node a,struct node b)
{
if(a.l == b.l )
return a.w < b.w ;
return a.l < b.l ;
}
int main()
{
int t,book[N];
int n,i,j,sumtime,sum,x;
scanf("%d",&t);
while( t --)
{
scanf("%d",&n);
for(i = 1; i <= n; i ++)
scanf("%d%d",&num[i].l ,&num[i].w );
sort(num+1,num+n+1,cmp);
memset(book,0,sizeof(book));
sumtime = 0;
sum = n;
for(i = 1; i <= n; i ++)
{
if(!book[i])
{
x = i;
book[i] = 1;
sum --;
for(j = i+1; j <= n; j ++)
{
if(num[x].l <= num[j].l &&num[x].w <= num[j].w&&!book[j])
{
book[j] = 1;
x = j;
sum --;
}
}
sumtime++;
}
if(sum <= 0)
break;
}
printf("%d\n",sumtime);
}
return 0;
}