|
Posted on 2009-09-09 21:34 Uriel 阅读(616) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 贪心
搞了很久的一题。。。 这题跟1065一样,还是两个月前做的,1065过了,3636一直TLE。。 原来的方法很恶心的。。要遍历很多遍知道所有的数都归类过,后来改了一下,还是TLE。。 无奈上网搜解题报告。。 http://hi.baidu.com/findthegateopen/blog/item/8d7694127d16b7d8f7039eb1.html感叹下,二分的思想真是神奇啊。。 贴下三个版本的代码。。
/**//*Problem: 3636 User: Gilhirith Memory: N/A Time: N/A Language: C++ Result: Time Limit Exceeded*/
#include<stdio.h> #include<stdlib.h> #include<string.h>
struct In{ int L; int W; }S[20010];
int i,x,sum,n,t,flag,y,z,r;
int cmp(const void *a,const void *b) { struct In *c = (In *)a; struct In *d = (In *)b; if(c->L != d->L) return c->L-d->L; else return c->W - d->W; }
int main() { scanf("%d",&t); while(t--) { // memset(S,0x00,sizeof(S)); scanf("%d",&n); x=n; for(i=0;i<n;i++) { scanf("%d %d",&S[i].L,&S[i].W); } sum=0; qsort(S,n,sizeof(S[0]),cmp); while(x>0) { flag=0; for(i=0;i<n;i++) { if(S[i].L==0)continue; else { if(flag==0) { sum++; x--; S[i].L=0; r=S[i].W; z=S[i].L; flag=1; continue; } else if(flag==1 && r<S[i].W && z<S[i].L) { x--; z=S[i].L; S[i].L=0; r=S[i].W; } else if(flag==1) { continue; } } } } printf("%d\n",sum); } return 0; }
/**//*Problem: 3636 User: Gilhirith Memory: N/A Time: N/A Language: C++ Result: Time Limit Exceeded*/
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
struct In{ int L; int W; }S[20010];
int t,i,j,n,sum,res[20010];
bool cmp(In a,In b) { if(a.L != b.L) return a.L > b.L; else return b.W > a.W; }
int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",&S[i].L,&S[i].W); res[i]=0; } sum=0; sort(S,S+n,cmp); for(i=1;i<n;i++) { for(j=0;j<i;j++) { if(S[i].L<=S[j].L && S[i].W>=S[j].W) { if(res[j]+1>res[i])res[i]=res[j]+1; } } if(sum<res[i])sum=res[i]; } printf("%d\n",sum+1); } // system("PAUSE"); return 0; }
/**//*Problem: 3636 User: Gilhirith Memory: 496K Time: 157MS Language: C++ Result: Accepted*/
#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std;
struct In{ int L; int W; }S[20010];
int t,i,j,n,sum,res[20010];
bool cmp(In a,In b) { if(a.L != b.L) return a.L < b.L; else return b.W < a.W; }
int Sov() { int T[20010],len=0,r,l,mid; memset(T,0,sizeof(T)); for(int i=0;i<n;i++) { l=0; r=len; while(l<r) { mid=(l+r)/2; if(T[mid]>=S[i].W)l=mid+1; else r=mid; } if(len==l)len++; T[l]=S[i].W; } return len; }
int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d %d",&S[i].L,&S[i].W); res[i]=0; } sort(S,S+n,cmp); printf("%d\n",Sov()); } return 0; }
|