Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

解题思路O(N)

Posted by yuer437 at 2012-12-03 19:33:24 on Problem 1083
用数组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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator