长L米,宽 W 米的草坪里装有 n 个浇灌喷头。每个喷头都装在草坪中心线上(离两边各 W/2 米)。我们知道每个喷头的位置(离草坪中心线左端的距离),以及它能覆盖到的浇灌范围。
请问:如果要同时浇灌整块草坪,最少需要打开多少个喷头?
Picture1
输入格式:
输入包含若干组测试数据。
第一行一个整数 T 表示数据组数;
每组数据的第一行是整数n 、L 和 W;
接下来的 n 行,每行包含两个整数,给出一个喷头的位置和浇灌半径(上面的示意图是样例输入第一组数据所描述的情况)。
输出格式:
输出一个数字,表示要浇灌整块草坪所需喷头数目的最小值。如果所有喷头都打开也不能浇灌整块草坪,则输出“-1”。
样例输入:
3
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
样例输出:
6
2
-1
约定:
n<=15000
就想不出来排序
题都快看蒙了,怎么做
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- LYSnowy 2022-02-05 16:19关注
贪心问题,因为是一块草地,所以要考虑长和宽,宽的话只需要在输入数据的时候考虑一下半径,如果半径小于等于宽的二分之一就直接略过,在考虑长的时候不能以喷水的最长去考虑,要考虑和草地的交点,同时要考虑交点和交点之间要连起来或者互相覆盖,交点的计算公式为:start=x-sqrt(radius^2-(w/2)^2),end=x+sqrt(radius^2-(w/2)^2),并把最后一个end求出来,如果大于长,就说明可以,否则输出-1.
#include<iostream> #include<algorithm> #include<stdio.h> #include<math.h> using namespace std; #define MAX_NUM 15001 typedef struct Sprayer { double location; double radius; double inter_point_start; double inter_point_end; }Spr[MAX_NUM]; int cmp(Sprayer a, Sprayer b) { return a.inter_point_start < b.inter_point_start; } int main() { int T; Spr spr; cin >> T; for (int k = 1; k <= T; k++) { int n, cnt = 0; double L, W; cin >> n >> L >> W; for (int i = 1; i <= n; i++) { cin >> spr[i].location >> spr[i].radius; if (spr[i].radius <= W / 2) continue; //cout<<"jiance"<<endl; cnt++; spr[cnt].inter_point_start = spr[i].location - sqrt(spr[i].radius * spr[i].radius - W * W / 4.0);//cout<<"a[cnt].x"<<"Ϊ"<<spr[cnt].inter_point_start<<endl; spr[cnt].inter_point_end = spr[i].location + sqrt(spr[i].radius * spr[i].radius - W * W / 4.0);//cout<<"a[cnt].x"<<"Ϊ"<<spr[cnt].inter_point_end<<endl; } sort(spr + 1, spr + cnt + 1, cmp); //cout<<"jiance2"<<endl; int min_num = 0; double Sum = 0; int flag = 1; int i = 1; while (Sum < L) { min_num++; double t = Sum; for (; spr[i].inter_point_start <= t && i <= cnt; i++)// if (Sum < spr[i].inter_point_end) { Sum = spr[i].inter_point_end; //cout<< Sum<<"是多少"; } if (t == Sum && t < L) { cout << "-1" << endl; flag = 0; break; } } if (flag) cout << min_num << endl; } }
本回答被题主选为最佳回答 , 对您是否有帮助呢?解决 无用评论 打赏 举报
悬赏问题
- ¥15 组策略中的计算机配置策略无法下发
- ¥15 机器学习简单问题解决
- ¥15 如何绘制动力学系统的相图
- ¥15 对接wps接口实现获取元数据
- ¥20 给自己本科IT专业毕业的妹m找个实习工作
- ¥15 用友U8:向一个无法连接的网络尝试了一个套接字操作,如何解决?
- ¥30 我的代码按理说完成了模型的搭建、训练、验证测试等工作(标签-网络|关键词-变化检测)
- ¥50 mac mini外接显示器 画质字体模糊
- ¥15 TLS1.2协议通信解密
- ¥40 图书信息管理系统程序编写