区间选点
学长原创：Click Here~
题目重述：
给n个闭区间[a,b]。取尽量少的点，使得每个区间都至少有一个点（不同区间内含的点可以是同一个）.
算法分析：
给b从小到大排序（b相同，则a从大到小）。从前往后遍历，当遇到新的区间时候，把这个区间的b作为新的区间的结束点。
出现的情况，总共会有两种。
一、一个区间被另一个区间所包含。则此时我们可以选择小的区间（[a1,b1]），因为小的区间所包含的点一定会被大区间包含，而大区间包含的点不一定会被小区间所包含。（如，图一）
二、两个区间没有包含关系。则，此时一定有a1 >= a2 >= a3....因为显然选择它的右端点是明智的。因为它比前面的点能覆盖更大的范围。（[A1,B1]）。（如，图二）
#include <stdio.h>
#include <algorithm>
using namespace std;
struct Extent
{
int a,b;
bool operator < (const Extent& S)const
{
return b < S.b || b == S.b && a > S.a;
}
}A[10002];
int main()
{
int z,n,cnt,end;
scanf("%d",&z);
while(z--)
{
cnt = 0;
end = -1;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%d",&A[i].a,&A[i].b);
sort(A,A+n);
for(int i=0;i<n;i++)
{
if(end < A[i].a)
{
end = A[i].b;
cnt++;
}
}
printf("%d\n",cnt);
}
return 0;
}
题目链接：Click Here ~
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 1e3 + 5;
struct Point
{
double a,b;
bool operator < (const Point tmp)const
{
if(a != tmp.a)
return a < tmp.a;
return b < tmp.b;
}
};
Point p[N];
int Find(int n)
{
int num = 1;
double cur = p[0].b;
for(int i = 1;i < n;++i)
{
if(p[i].a - cur > 1e-5) //p[i].a > cur
{
num++;
cur = p[i].b;
}else
{
if(p[i].b - cur < 1e-5) // cur > p[i].b
cur = p[i].b;
}
}
return num;
}
int main()
{
int n,d,kase = 1;
while(scanf("%d%d",&n,&d),(n||d))
{
bool flag = false;
double x,y,tmp;
for(int i = 0;i < n;++i){
scanf("%lf%lf",&x,&y);
tmp = sqrt(d*d-y*y);
p[i].a = x - tmp;
p[i].b = x + tmp;
if(y > d) flag = true;
}
sort(p,p+n);
if(flag){
printf("Case %d: -1\n",kase++);
continue;
}
int res = Find(n);
printf("Case %d: %d\n",kase++,res);
}
return 0;
}