http://blog.csdn.net/v5zsq/article/details/46790025
Description
有一些木材和一台机器。机器每次加工一根木材需要的时间是1，但是当加工木材的长度和宽度都小于等于前一根木材的时候，不需要时间。求最少需要多少时间加工完所有的木材 Input 第一行为数据组数t，每组用例第一行为木材数量n，然后是每根木材的长度和宽度 Output 对于每组用例，输出最短加工时间 Sample Input 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 Sample Output 2 1 3 Solution
由于切一根最长最宽的就可以不切比它短和窄的，反过来就是切一根最短最细的就不用切比它长和宽的，所以将木材升序排之后，从最短的开始切，用标记数组表示是否切此根木材，每切一根就把比它长和宽的标记，最后记录没被标记的木材即为需要切的木材数量
#include<iostream> #include<algorithm> #include<queue> #include<vector> #include<string> #include<cstring> #include<cstdio> const int maxn=100005; const int INF=0x3f3f3f3f; typedef long long LL; using namespace std; struct node { int l,w; }P[maxn]; bool cmp(node a,node b) { return a.l==b.l?a.w<b.w:a.l<b.l; } int used[maxn]; //0表示切，1不切 int main() { // freopen("E:\\ACM\\test.txt","r",stdin); int T,N; cin>>T; while(T--) { cin>>N; memset(used,0,sizeof(used)); //初始化所有木块都要切 for(int i=0;i<N;i++) cin>>P[i].l>>P[i].w; sort(P,P+N,cmp); for(int i=0;i<N;i++) { if(used[i]) continue; //已经可以不用切的木块 int t=i; for(int j=i+1;j<N;j++) { if(!used[j]&&P[j].l>=P[t].l&&P[j].w>=P[t].w) { t=j; used[j]=1; //这块木块可以不用切 } } } int ans=0; for(int i=0;i<N;i++) if(!used[i]) ++ans; //要切的木块就是答案 cout<<ans<<endl; } return 0; }
