題目描述
噴水裝置（二）
時(shí)間限制：3000 ms | 內(nèi)存限制：65535 KB
難度：4
描述
有一塊草坪一也，橫向長(zhǎng)w,縱向長(zhǎng)為h,在它的橫向中心線上不同位置處裝有n(n<=10000)個(gè)點(diǎn)狀的噴水裝置棠绘，每個(gè)噴水裝置i噴水的效果是讓以它為中心半徑為Ri的圓都被潤(rùn)濕。請(qǐng)?jiān)诮o出的噴水裝置中選擇盡量少的噴水裝置，把整個(gè)草坪全部潤(rùn)濕瘟芝。
輸入
第一行輸入一個(gè)正整數(shù)N表示共有n次測(cè)試數(shù)據(jù)踊跟。
每一組測(cè)試數(shù)據(jù)的第一行有三個(gè)整數(shù)n,w,h，n表示共有n個(gè)噴水裝置玛痊，w表示草坪的橫向長(zhǎng)度，h表示草坪的縱向長(zhǎng)度狂打。
隨后的n行卿啡，都有兩個(gè)整數(shù)xi和ri,xi表示第i個(gè)噴水裝置的的橫坐標(biāo)（最左邊為0），ri表示該噴水裝置能覆蓋的圓的半徑菱父。
輸出
每組測(cè)試數(shù)據(jù)輸出一個(gè)正整數(shù)颈娜，表示共需要多少個(gè)噴水裝置，每個(gè)輸出單獨(dú)占一行浙宜。
如果不存在一種能夠把整個(gè)草坪濕潤(rùn)的方案官辽，請(qǐng)輸出0。
樣例輸入
2
2 8 6
1 1
4 5
2 10 6
4 5
6 5
樣例輸出
1
2
題目鏈接
題目分析：本題可以看作是區(qū)間覆蓋問(wèn)題的一個(gè)例子粟瞬，只要對(duì)上述的內(nèi)容稍微轉(zhuǎn)換以下即可同仆，將每個(gè)圓的射擊范圍映射到區(qū)間內(nèi)∪蛊罚可相應(yīng)轉(zhuǎn)換為：數(shù)軸上有n個(gè)區(qū)間[ai,bi]（這個(gè)指的是噴水裝置的合理的噴水區(qū)間）俗批，選擇盡量少的區(qū)間覆蓋一條指定線段[s,t]（這個(gè)區(qū)間指的就是[0,w]）俗或。
用一副圖描述一下或許更清楚一些
半徑的平方減去 高度一半的平房開(kāi)根號(hào) 乘以2 會(huì)得到 該噴水裝置 所覆蓋 草的寬度 只要用最少的噴水裝置 覆蓋寬度加起來(lái)大于等于草坪的寬度 就完成啦
下面用貪心策略解題：
把各區(qū)間按照a從小到大排序，從前向后遍歷岁忘，然后每次選擇從當(dāng)前起點(diǎn)S開(kāi)始的最長(zhǎng)區(qū)間辛慰，并以這個(gè)區(qū)間的右端點(diǎn)為新的起點(diǎn)，繼續(xù)選擇干像，直到找不到區(qū)間覆蓋當(dāng)前起點(diǎn)S或者S已經(jīng)到達(dá)線段末端帅腌。
不多說(shuō)直接上代碼
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
public class PSZZ2 {
public static void main(String args[]) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
List <Data> list;
for(int i=0;i<n;i++) {
int num=0,w=0,h=0;
list =new ArrayList<Data>();
num=s.nextInt();
w=s.nextInt();
Data data=new Data();
h=s.nextInt();
for(int j=0;j<num;j++) {
data=new Data();
data.left=s.nextInt();
double temp=s.nextInt();
temp=Math.sqrt(temp*temp-h/2*h/2);
if(temp > h/2.0) {
data.right=data.left+temp;
data.left=data.left-temp;
list.add(data);
}
}
Collections.sort(list, new Comparator<Data>() {
public int compare( Data o1, Data o2) {
return o1.left>o2.left?1:-1;
}
});
double right=0.0; //保存當(dāng)前 已經(jīng)覆蓋的寬度
int count=0; //需要的草坪數(shù)字
while(right<w)
{
double m=0.0; //存放當(dāng)前的最優(yōu)解
for(int j=0;j<list.size()&&list.get(j).left<=right;j++)
{
if(list.get(j).right-right>m) m=list.get(j).right-right;
}
if(m!=0)
{
count++;
right+=m;
}
else break;
}
if(right<w)System.out.println(0);
else System.out.println(count);;
}
}
static class Data{
public double left;
public double right;
}
}
githup 源碼地址 https://github.com/haha174/daylx
個(gè)人博客地址 http://www.haha174.top/article/details/253896
推薦一篇文章 http://mp.weixin.qq.com/s/_WOG1uQezfpgx873vI2upg
