喷水装置（二）-NYOJ

描述

有一块草坪，横向长w,纵向长为h,在它的橫向中心线上不同位置处装有n(n<=10000)个点状的喷水装置，每个喷水装置i喷水的效果是让以它为中心半径为Ri的圆都被润湿。请在给出的喷水装置中选择尽量少的喷水装置，把整个草坪全部润湿。

输入

第一行输入一个正整数N表示共有n次测试数据。
每一组测试数据的第一行有三个整数n,w,h，n表示共有n个喷水装置，w表示草坪的横向长度，h表示草坪的纵向长度。
随后的n行，都有两个整数xi和ri,xi表示第i个喷水装置的的横坐标（最左边为0），ri表示该喷水装置能覆盖的圆的半径。

输出

每组测试数据输出一个正整数，表示共需要多少个喷水装置，每个输出单独占一行。
如果不存在一种能够把整个草坪湿润的方案，请输出0。

样例输入

2
2 8 6
1 1
4 5
2 10 6
4 5
6 5

样例输出

1
2

在这之前 做了两道类似的 代码如下：

/*
直线上有N个点 点I的位置是Xi 从这N个点中选取若干个 跟他们做上标记 对每个点
其距离为R以内的区域必须带有标记的点(自己本身带有标记的点 可以认为与其距离为0的地方有一个
带有标记的点)。在满足这个条件的情况下 希望能尽可能少的点添加标记 。请问至少有多少点被加上标记
在满足这个条件的情况下，希望能尽可能少的点添加标记 请问至少要有多少点被标记？
1<=N<=1000
0<=R<=1000
0<=Xi<=1000
EG:s
输入: N=6  R=10 X={1,7,15,20,50}
输出3 如下图所示:-----------·-------------·----------·---------
-1------7-------15-----20-------30--------------->如上图所示
解：我们从最左边开始 对于最左边的点开始 距离为R的区域内必须有标记的点、显然带有这个标记的一定在此点的右侧（包括自己）
那究竟要给那个点加上标记呢 答案应该是从最左边的点开始
距离为R以内的最远的点。因为左边的区域没有点所以应该尽可能的覆盖靠右边的点
当加入了第一个标记后 将R的范围内去掉  此时又会出现一个最左的点 再按照同样的方法 再所有得点被重复之前
不断地重复这个过程 贪心算法
*/
# include <stdio.h>
# define MAX 1000
int main(){int N,R,X[MAX]={0};int i,Flag=0,Left,NEW;scanf("%d %d",&N,&R);for(i=0;i<N;i++)scanf("%d",&X[i]);i=0;while(i<N)   //i用来记数 其数值等于从左边经过的点的数目一共N个{Left=X[i++];//Left为每次循环的最左边的点while(i<N&&X[i]<=Left+R)i++;//一直向右直到出现距离Left距离大于R的点NEW=X[i-1];                       //NEW为加上标记的点的位置while(i<N&&X[i]<=NEW+R)i++&&Flag++;//一直向右直到出现距离NEW距离大于R的点               //此时确定一个标记的点}printf("%d\n",Flag);return 0;
}

2：

/*
有n项工作，每项工作分别在时间开始，在时间结束。
对于每项工作，你都可以选择参与与否。如果选择了参与，
那么自始至终都必须全程参与。此外，参与工作的时间段不能重叠（闭区间）。
你的目标是参与尽可能多的工作，那么最多能参与多少项工作？
N∈[1,100000]  S,T∈[1,10^9]解：
最大区间调度问题。在此我们进行细分，将该问题命名为最多区间调度问题，因为该问题的目标是求不重叠的最多区间个数，而不是最大的区间长度和。
最简单的区间调度问题，贪心算法求解，
贪心策略：
在可选的工作中，每次都选取结束时间最早的工作。
EG:
输入:N=5
S={1,2,4,6,8}
T={3,5,7,9,10}
输出:3
(选择1 3 5 工作)
*/
# include <stdio.h>
# define N 100
void paixu(int A[][N],int n);//选择排序 当数量很大时 用快速排序 这里就不改了 
void SWEP(int *a,int *b);//交换函数
int A[2][N];
int main(){int i,n,sum=0,t=0;//sum记录公祖豆儿数量 t记录结束时间scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&A[0][i]);//A[0]->Sfor(i=0;i<n;i++)scanf("%d",&A[1][i]);//A[1]->Tpaixu(A,n);//排序时以A[1]为比较对象for(i=0;i<N;i++){if(t<A[0][i])sum++;t=A[1][i];}printf("%d",sum);return 0;
}
void paixu(int A[][N],int n)
{int i,j,k;for(i=0;i<n-1;i++){k=i;for(j=i+1;j<n;j++)if(A[1][j]>A[1][k])k=j;if(k!=i){SWEP(&A[0][i],&A[0][k]);SWEP(&A[1][i],&A[i][k]);}	}
}
void SWEP(int *a,int *b)
{int temp=*a;*a=*b;*b=temp;
}

本质是一样的 

不过喷水装置 需要注意的就是 只有R²-H²>0时 这个装置才是有效的

用了快排  和区间调度是一样的

代码AC情况：

代码<C语言>：

# include <stdio.h>
# include <math.h>
# define N 1000
typedef double elem;
# define max(a,b) (a)>(b)?(a):(b)
void  KuaiPai(elem A[][N],int left,int right);//快速排序 自身实现
void change(elem *A,elem *B)//交换函数
{elem C=*A;*A=*B;*B=C;
}
double PS[2][N],d,hw,h,MAX,sum;
int T,num,W,H,i,j,X,R;
int main(){//freopen("SASA.txt","r",stdin);scanf("%d",&T);while(T--){scanf("%d%d%d",&num,&W,&H);h=H*0.5;hw=h*h;for(j=i=0;i<num;i++){scanf("%d%d",&X,&R);if(R>h){//只对符合条件的装置计数d=sqrt(R*R-hw);PS[0][j]=X-d;PS[1][j++]=X+d;//符合条件的装置的个数=j}}sum=num=0;//每次初始化为0KuaiPai(PS,0,j-1);//对符合条件的装置 下标[0,j-1]while(sum<W){MAX=0;//用MAX来记录最长的更新的距离for( i=0;i<j&&PS[0][i]<=sum;i++) //每一次遍历找最长的更新距离，并且起点至少在sum以内MAX=max(MAX,(PS[1][i]-sum));//筛选最大值if(MAX){//如果最大值不是 0  说明没有断层num++;//记数sum+=MAX;}else break;}printf("%d\n",MAX?num:0);//输出}return 0;
}
void  KuaiPai(elem A[][N],int left,int right)
{int i=left,j=right;elem temp=A[0][left];//记录一下if(left>=right)  return;//如果重合while(i!=j){while(A[0][j]>=temp && i<j)j--;//从右向左找while(A[0][i]<=temp && i<j)i++;//从左向右找if(i<j){change(&A[0][i],&A[0][j]);//交换change(&A[1][i],&A[1][j]);}
}change(&A[0][left],&A[0][i]);//换回来change(&A[1][left],&A[1][i]);KuaiPai(A,left,i-1);//左递归KuaiPai(A,i+1,right);//右递归
}