| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
解题思路O(N)用数组d[401]记录每个房间前的走廊被用过多少次,则答案即为d[i]*10;每扫描一个点将数组这个范围内的值加1,注意,范围的确定,若下限为偶数,则下限需减一,若上限为奇数,则上限需加1,例如,s=4,t=7时,房间4到房间7之间的走廊都要占用,而房间4前的走廊与房间3之间的走廊是一样的,房间7与房间8之间的走廊也是一样的,所以要扩大数组的更新范围为[3,8]。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Max(a,b) a>b?a:b
#define Min(a,b) a<b?a:b
int d[401];
int main()
{
int i,j,T,N,s,t,mn,mx;
scanf("%d",&T);
while(T--)
{
scanf("%d",&N);
for(i=0;i<N;i++)
{
scanf("%d%d",&s,&t);
mn=Min(s,t);
mx=Max(s,t);
if(mn%2==0)
mn--;
if(mx%2==1)
mx++;
for(j=mn;j<=mx;j++)
d[j]++;
}
s=0;
for(i=1;i<401;i++)
if(s<d[i])
s=d[i];
printf("%d\n",s*10);
memset(d,0,sizeof(d));
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator