2814 - 棍子
时间限制 : 1 秒
内存限制 : 128 MB
这里有n个木棍，我们已知它们的长度和重量。这些棍子会一个接一个在机器中加工，把棍子放入需要些时间
，称作设置时间。这些设置时间花费在清理设备和改变工具，形状。
设置机器时间需要：
1.设置第一个木棍需要1分钟
2.之后加工设木棍的长度l和重量w，如果后面的木棍l'(前面的木棍)<=l和w'<=w则不需要加工时间，否则需要一分钟。
你需要找到设置n个木棍所需设置时间最少。例如，你有5根木棍他们都长度和重量分别为(4,9), (5,2),
(2,1), (3,5), 和 (1,4)，他们所需最少时间为2分钟，按照 (1,4), (3,5), (4,9), (2,1), (5,2).
题目输入
输入格式：
第一行T表示T个案例。每组案例有2行，第一行为一个整数n，1<=n<=5000,表示有n个木棍，第2行有2n个整数l1,w1,
l2,w2.....l,w最多为10000
题目输出
输出格式:
每行含有每组最少的设置时间。
输入/输出样例
输入格式
3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1
输出格式
2 1 3
C++解答
#include<stdio.h> #include <algorithm> using namespace std; typedef struct node { int len,wei; }; int cc( const node& a, const node& b ) { return ( a.len < b.len || ( a.len == b.len && a.wei < b.wei ) ); } int main() { int t;scanf("%d",&t); while(t--) { int n;scanf("%d",&n); node k[5000]; int as[5000]={0}; for (int i=0;i<n;i++) scanf("%d%d",&k[i].len,&k[i].wei); sort(k,k+n,cc); int sum=0; for (int i=0;i<n;i++) if(!as[i]) { sum++; as[i]=1; int ww=k[i].wei; for (int kk=i+1;kk<n;kk++) if (!as[kk]&&k[kk].wei>=ww) { as[kk]=1; ww=k[kk].wei; } } printf("%d\n",sum); } return 0; }