讨论 / 为什么我的程序全部超时?
drcool 2014-01-19 06:27:25
点我顶贴 收藏 删除
查找用的是二分,难道不够快?

#include <stdio.h>

#include <stdlib.h>

struct sc{

int s;

int id;

};

struct sc T[1000];

struct st{

int a,b;

};

struct st W[500000];

int n,m;

int compare1( const void *arg1, const void *arg2 )

{

struct sc *A=arg1, *B=arg2;

return A->id-B->id;

}

int compare2( const void *arg1, const void *arg2 )

{

struct st *A=arg1, *B=arg2;

return A->a-B->a;

}

int bsear(int x)

{

int l=0,r=m-1;

int mid;

while(l<=r)

{

mid=(l+r)/2;

if(T[mid].id==x) return mid;

if(T[mid].id<x) l=mid+1;

else r=mid-1;

}

return -1;

}

int main()

{

int i,j,p;

scanf("%d%d",&n,&m);

for(i=0;i<m;i++)scanf("%d",&T[i].s);

for(i=0;i<m;i++)scanf("%d",&T[i].id);

for(i=0;i<n;i++)scanf("%d%d%d",&W[i].a,&W[i].b,&j);

scanf("%d",&p);

qsort(T,m,sizeof(struct sc),compare1);

qsort(W,n,sizeof(struct st),compare2);

for(i=n-1;i>=0;i--)

{

if(W[i].a==p) break;

j=bsear(W[i].b);

if(T[j].s) T[j].s--;

}

for(i=0;i<m;i++)

if(T[i].s) break;

if(i==m) printf("0");

else printf("%d",T[i].id);

}

查看更多回复
提交回复