|
|
Posted on 2009-09-09 21:34 Uriel 閱讀(630) 評論(0) 編輯 收藏 引用 所屬分類: POJ 、 貪心
搞了很久的一題。。。 這題跟1065一樣，還是兩個月前做的，1065過了，3636一直TLE。。 原來的方法很惡心的。。要遍歷很多遍知道所有的數(shù)都?xì)w類過，后來改了一下，還是TLE。。 無奈上網(wǎng)搜解題報告。。 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;
}
|