杭电acm 1025,为何总是提示超时??!!
总是提示超时,蛋疼了,测试了好几组用例都正确的啊。
因为刚开始考虑输入中 贫困地区出现顺序不一定是递增的,所以没有用求最长递增字串的方式解。直接自己写的
ACM 杭电
#include <stdio.h>
#include <stdlib.h>
#define N 500000
typedef struct
{
int poor;
int rich;
} Road;
int intersection[N]={0};//记录第i条数据和其它记录的交点个数
int n,interNodeCount=0;//记录总共的交点个数
int caseCount=0;
void func_1025()
{
int i,max=0,nodeCount=0,k=0;
while (interNodeCount>0)
{
for (i=0;i<n;i++)
{
if (intersection[i]>max)
{
max=intersection[i];
k=i;
}
}
intersection[k]=0;
interNodeCount-=max;
++nodeCount;
}
if (n-nodeCount==1)
{
printf("Case %d:\nMy king, at most %d road can be built.\n\n",++caseCount,n-nodeCount);
}
else
{
printf("Case %d:\nMy king, at most %d roads can be built.\n\n",++caseCount,n-nodeCount);
}
}
void main()
{
int poor,rich,i,j;
Road *r=(Road*)malloc(sizeof(Road)*N);
while(scanf("%d",&n)!=EOF)
{
interNodeCount=0;
for (i=0;i<n;i++)
{
r[i].poor=r[i].rich=0;
intersection[i]=0;
scanf("%d%d",&r[i].poor,&r[i].rich);
for (j=0;j<i;j++)
{
if ((r[j].poor<r[i].poor&&r[j].rich>r[i].rich)||(r[j].poor>r[i].poor&&r[j].rich<r[i].rich))
{
intersection[i]++;
interNodeCount++;
intersection[j]++;
}
}
}
func_1025();
}
}