http://acm.hdu.edu.cn/showproblem.php?pid=5124

lines

Time Limit: 5000/2500 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1362 Accepted Submission(s): 566

Problem Description

John has several lines. The lines are covered on the X axis. Let A is a point which is covered by the most lines. John wants to know how many lines cover A.

Input

The first line contains a single integer T(1≤T≤100)(the data for N>100 less than 11 cases),indicating the number of test cases.
Each test case begins with an integer N(1≤N≤105),indicating the number of lines.
Next N lines contains two integers Xi and Yi(1≤Xi≤Yi≤109),describing a line.

Output

For each case, output an integer means how many lines cover A.

Sample Input

1 2

2 2

2 4

3 4

5 1000

1 1

2 2

3 3

4 4

5 5

Sample Output

Source

BestCoder Round #20

一个离散化，我也是醉了，怎么就搞不懂了。。。。

这题居然能不用离散化，暴力水过，还是会离散化好点，但是这个水代码也粘贴下吧！！！

#include<stdio.h>

#include<string.h>

#define N 1100000

#define max(a,b) (a>b?a:b)

int a[N];

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

      int n, i, L, R;

      scanf("%d", &n);

      memset(a, , sizeof(a));

      for(i=; i<=n; i++)

      {

          scanf("%d%d", &L, &R);

          a[L] ++;

          a[R+] --;

      }

      int Max = a[], sum=a[];

      for(i=; i<N; i++)

      {

          sum += a[i];

          Max = max(Max, sum);

      }

      printf("%d\n", Max);

    }

    return ;

}

水过代码

下面两个代码都是用了离散化，但是其实我并不怎么懂离散化，只懂了一点点，继续学习吧！！！

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#include<math.h>

using namespace std;

#define N 201000

struct node

{

    int L, R;

}a[N];

int b[N], V[N];

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

       int i, L, R, n, k=;

       scanf("%d", &n);

       memset(a, , sizeof(a));

       memset(b, , sizeof(b));

       memset(V, , sizeof(V));

       for(i=; i<n; i++)

       {

           scanf("%d%d", &a[i].L, &a[i].R);

           b[k++] = a[i].L;

           b[k++] = a[i].R;

       }

       sort(b, b+k);

       int z = unique(b, b+k)-b;

       for(i=; i<n; i++)

       {

           L = lower_bound(b, b+z, a[i].L) - b;

           R = lower_bound(b, b+z, a[i].R) - b;

           V[L]++;

           V[R+]--;

       }

       int sum=V[], Max = V[];

       for(i=; i<N; i++)

       {

           sum += V[i];

           Max = max(Max, sum);

       }

       printf("%d\n", Max);

    }

    return ;

}

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <map>

using namespace std;

#define N 200005

struct node

{

    int L, R;

}a[N];

int V[N], b[N];

map<int, int>dic;

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        int i, j, k=, n, L, R;

        scanf("%d", &n);

        memset(a, , sizeof(a));

        memset(V, , sizeof(V));

        memset(b, , sizeof(b));

        for(i=; i<n; i++)

        {

            scanf("%d%d", &a[i].L, &a[i].R);

            b[k++] = a[i].L;

            b[k++] = a[i].R;

        }

        sort(b, b+k);

        j=;

        for(i=; i<k; i++)

        {

           if(i==)

                dic[b[i]]=j++;

           else if(b[i]!=b[i-])

                dic[b[i]]=j++;

        }

        for(i=; i<n; i++)

        {

            L = dic[a[i].L];

            R = dic[a[i].R];

            V[L]++;

            V[R+]--;

        }

        int Max = V[], sum = V[];

        for(i=; i<N; i++)

        {

            sum += V[i];

            Max = max(Max, sum);

        }

        printf("%d\n", Max);

    }

    return ;

}

巴特西

（树状数组+离散化）lines--hdu --5124

lines

最新文章

热门文章