HDU 4343 D - Interval query 二分贪心

D - Interval query
Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=88748#problem/D

Description

This is a very simple question. There are N intervals in number axis, and M queries just like “QUERY(a,b)” indicate asking the maximum number of the disjoint intervals between (a,b) .

Input

There are several test cases. For each test case, the first line contains two integers N, M (0<N, M<=100000) as described above. In each following N lines, there are two integers indicate two endpoints of the i-th interval. Then come M lines and each line contains two integers indicating the endpoints of the i-th query.
You can assume the left-endpoint is strictly less than the right-endpoint in each given interval and query and all these endpoints are between 0 and 1,000,000,000.

Output

For each query, you need to output the maximum number of the disjoint intervals in the asked interval in one line.

Sample Input

3 2
1 2
2 3
1 3
1 2
1 3

Sample Output

1
2

HINT

题意

给你n个线段

m次询问，问你在ab区间内，最多放下几个不能相互重叠的线段

题解：

直接n*m暴力

首先，我们按照右端点排序，然后能放进去就放进去，这种策略肯定是最优的

然后就暴力吧……15s

有两个想一想好像并咩有什么用的剪枝：

预处理出来第一个能放进区间的线段

预处理出哪些线段永远都不可能选的

代码：

#include<stdio.h>

#include<iostream>

#include<string.h>

#include<algorithm>

#define maxn 110000

using namespace std;

struct node

{

    int x,y;

};

bool cmp(node a,node b)

{

    if(a.y==b.y)

        return a.x<b.x;

    return a.y<b.y;

}

node a[maxn];

node b[maxn];

node qq[maxn];

int cc[maxn];

//node b[maxn];

int tot=;

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        tot=;

        memset(a,,sizeof(a));

        memset(b,,sizeof(b));

        memset(qq,,sizeof(qq));

        memset(cc,,sizeof(cc));

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

            scanf("%d %d",&a[i].x,&a[i].y);

        sort(a,a+n,cmp);

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

        {

            int flag=;

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

            {

                if(a[j].y>a[i].y)

                    break;

                if(a[j].x<a[i].x)

                    continue;

                flag=;

                break;

            }

            if(!flag)

                b[tot++]=a[i];

        }

        int x,y,ans;

        for(int i=;i<m;i++)

        {

            scanf("%d%d",&qq[i].x,&qq[i].y);

            int l=,r=tot-;

            x = qq[i].x;

            y = qq[i].y;

            while(l<=r)

            {

                int mid=(l+r)>>;

                if(b[mid].y<=x)

                    l=mid+;

                else

                    r=mid-;

            }

            cc[i]=l;

        }

        for(int i=;i<m;i++)

        {

            x = qq[i].x,y = qq[i].y;

            ans=;

            int tmp=x;

            int l = cc[i];

            for(int j=l;j<tot;j++)

            {

                if(b[j].y<=y)

                {

                    if(b[j].x<tmp)

                        continue;

                    tmp = b[j].y;

                    ans++;

                }

                else

                    break;

            }

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

        }

    }

}

巴特西

HDU 4343 D - Interval query 二分贪心

最新文章

热门文章