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);
}
}
}