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

土办法,直接从后向前,分割递归

Posted by endlesscpp at 2012-03-21 00:22:11 on Problem 2528
static const int NMAX = 10000;
static int sl[NMAX]; //left endpoint
static int sr[NMAX]; //right endpoint
static char flag[NMAX];
static const int MAX_LEN = 10000000;
static int N; // the N input intervals

void calc(int l, int r, int i)
{
    if (i < 0)
        return;

    int l2 = sl[i];
    int r2 = sr[i];

    if (l2 <= r && r2 >= l)
        flag[i] = 1;
    
    if (r2 < r)
    {
        int t = (r2+1) < l ? l : (r2+1);
        calc (t, r, i-1);
    }

    if (l2 > l)
    {
        int t = (l2-1) > r ? r : (l2-1);
        calc(l, t, i-1);
    }
}

static void processcase()
{
    int lmin = 100000000;
    int lmax = 0;
    memset(flag, 0, sizeof(flag));

    scanf("%d", &N);
    for (int i = 0; i<N; i++)
        scanf("%d %d", &sl[i], &sr[i]);

    calc(1, MAX_LEN, N-1);

    int total = 0;
    for (int i = 0; i<N; i++)
        if (flag[i] != 0)
            total++;

    printf("%d\n", total);
}

int main()
{
    int ncase = 0;
    scanf("%d", &ncase);
    for (int i = 0; i<ncase; i++)
    {
        processcase();
    }
    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