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