| ||||||||||
| 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 | |||||||||
土办法,直接从后向前,分割递归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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator