题目描述 Lialosiu要制作木棍，给n根作为原料的木棍的长度和重量。根据要求求出制作木棍的最短时间。
首先我们知道制作第一个木棍需要1分钟，若是接着要制作的木棍的重量和长度都不少于当前的木棍，那么就不需要建立的时间，若是没有，则再需要建立时间，也就是1分钟。
举个例子，如果你有五个原料木棍，他们的长度和重量分别是(4,9), (5,2), (2,1), (3,5), 和 (1,4), 那么第一分钟你要建立一根木棍作为起始参照，比如(1,4)接下来(3,5)和(4,9)都可以不花费时间，然后用第二分钟选取(2,1)这跟木棍作为参照，接下来(5,2)可以不花费任何时间，总的来说，你一共花费了两分钟，这也是你可能使用的最少时间。
现在给了n个木棍的长度和重量，你能求出使用这些木棍的最少时间吗？
输入 首先，输入一个正整数T ,代表有T组数据。
接下来，第二行你要输入正整数n（1<=n<=5000）代表的你的原料木棍个数。
第三行你要输入2*n 个 正整数l1, w1, l2, w2, …, ln, wn，每一个数字都不超过10000 。 li代表第i根木棍的长度，wi代表第i根木棍的重量。
输出 输出一个整数，代表最少需要的时间t。
样例输入 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
#include<stdio.h>#include<algorithm>#define MAX_N 5002using namespace std;struct S{int l,w;};bool vis[MAX_N];S que[MAX_N],res[MAX_N];bool cmp(S x,S y){ if(x.l==y.l) return x.w<y.w; return x.l<y.l;}int main(){ int T,n; scanf("%d",&T); while(T--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d%d",&res[i].l,&res[i].w); sort(res,res+n,cmp); int u=0; for(int i=0;i<n;i++){ bool update=false; for(int j=0;j<u;j++){ if(que[j].l<=res[i].l&&que[j].w<=res[i].w){ que[j]=res[i]; update=true; break; } } if(!update) que[u++]=res[i]; } PRintf("%d/n",u); } return 0;}新闻热点
疑难解答
