HDU - 1051 Wooden Sticks
有一堆n个木棍。每个棒的长度和重量是预先知道的。木棒要用木工机械逐一加工。它需要一些时间，称为设置时间，机器准备加工一根棍子。安装时间与清洗操作和更换机器中的工具和形状有关。木工机床的安装时间如下：
（a）第一根木棍的安装时间为1分钟。
(b)在加工长度l和重量w的棒材之后，如果l<=l'和w<=w'，机器将不需要长度l'和重量w'的棒材的安装时间。否则，安装需要1分钟。
你要找到最小的设置时间来处理给定的一堆木棒。例如，如果有5根棍子的长度和重量对(4,9)、(5,2)、(2,1)、(3,5)和(1,4)，那么最小设置时间应该是2分钟，因为存在一系列对(1,4)、(3,5)、(4,9)、(2,1)、(5,2)。
对于题目例子中的(4,9)、(5,2)、(2,1)、(3,5)和(1,4)，经过排序后得到的是(1，4)、（2，1），(3，5)，（4，9），（5，2）
首先从（1，4）开始向右搜索，发现（2，1）未被计算过，但是不满足情况，那么将该位置记为start（每次搜索前被赋值为n（坐标点的个数）），作为下次搜索的起点，继续向右发现(3，5)满足情况，那么重新将(3，5)作为与下一个比较的点并且标记为已计算，与（4，9）比较，满足情况，则（4，9）与（5，2）比较发现不满足情况，但是已到达尾部，开始下一次搜索，开始位置为start，即（2，1），由于(3，5)，（4，9）已经被标记为计算过，将与（5，2）进行匹配，成功，标记为已计算，没有发现匹配不成功的情况，故start位置为n，下次匹配不会进行，即完成全部计算
#include <iostream> #include <cmath> #include <math.h> #include <string> #include <cstdio> #include <algorithm> using namespace std; struct node{ int a,b,c; }n[10010]; bool cmp(node p1,node p2) { if(p1.a == p2.a) return p1.b < p2.b; return p1.a < p2.a; } int main() { int t,m,ans = 0; scanf("%d",&t); while(t--) { ans = 0; scanf("%d",&m); for(int i=1;i<=m;i++) { scanf("%d%d",&n[i].a,&n[i].b); n[i].c = 1; } sort(n+1,n+1+m,cmp); int k = 1; int temp = 0; while(temp != m){ int x = 0,y = 0; for(int i=k;i<=m;i++) if(n[i].c){ k = i; break; } for(int i=k;i<=m;i++) { if(!n[i].c) continue; if(n[i].a >= x && n[i].b >= y){ temp++; n[i].c = 0; x = n[i].a; y = n[i].b; } } ans++; } cout<<ans<<endl; } return 0; }
网易公司福利 162人发布
