poj 3069 Saruman's Army 贪心模拟
Saruman's Army
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 18794 | Accepted: 9222 |
Description
Saruman the White must lead his army along a straight path from Isengard to Helm’s Deep. To keep track of his forces, Saruman distributes seeing stones, known as palantirs, among the troops. Each palantir has a maximum effective range of R units, and must be carried by some troop in the army (i.e., palantirs are not allowed to “free float” in mid-air). Help Saruman take control of Middle Earth by determining the minimum number of palantirs needed for Saruman to ensure that each of his minions is within R units of some palantir.
Input
The input test file will contain multiple cases. Each test case begins with a single line containing an integer R, the maximum effective range of all palantirs (where 0 ≤ R ≤ 1000), and an integer n, the number of troops in Saruman’s army (where 1 ≤ n ≤ 1000). The next line contains n integers, indicating the positions x1, …, xn of each troop (where 0 ≤ xi ≤ 1000). The end-of-file is marked by a test case with R = n = −1.
Output
For each test case, print a single integer indicating the minimum number of palantirs needed.
Sample Input
0 3 10 20 20 10 7 70 30 1 7 15 20 50 -1 -1
Sample Output
2 4
Hint
In the first test case, Saruman may place a palantir at positions 10 and 20. Here, note that a single palantir with range 0 can cover both of the troops at position 20.
In the second test case, Saruman can place palantirs at position 7 (covering troops at 1, 7, and 15), position 20 (covering positions 20 and 30), position 50, and position 70. Here, note that palantirs must be distributed among troops and are not allowed to “free float.” Thus, Saruman cannot place a palantir at position 60 to cover the troops at positions 50 and 70.
题意:输入n个点和雷达扫描半径R;问覆盖所有点最少需要多少个雷达
#include<iostream> #include<string.h> #include<string> #include<algorithm> #include<queue> #include<set> using namespace std; int a[1005]; int n,cnt,r; int main() { while(cin>>r>>n&&r!=-1&&n!=-1) { for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int i=0,cnt=0; while(i<n)//一个标记能覆盖的范围[s+r,p+r],超出这个范围就加一个标记 { int s=a[i++];//能被覆盖的最左端的点的位置 while(i<n&&a[i]<=s+r) i++; int p=a[i-1];//标记的位置 while(i<n&&a[i]<=p+r) i++; cnt++; } cout<<cnt<<endl; } }
相关文章
- 理解 uptime 的:“平均负载”? 如何模拟测试
- 2020.05.02【NOIP普及组】模拟赛C组31总结
- 2020.04.29【NOIP普及组】模拟赛C组30总结
- 【CSS3】纯CSS代码实现模拟时钟,+js对时功能。
- ZOJ 3804 YY's Minions (简单模拟)
- Java实现 LeetCode 830 较大分组的位置(暴力模拟)
- Java 第十一届 蓝桥杯 省模拟赛 计算机存储中有多少字节
- Android模拟聊天工具
- 重新整理数据结构与算法——单双链表模拟队列[四]
- 《安富莱嵌入式周报》第292期:树莓派单片机100M双通道示波器开源,MDK5.38发布,万用表单芯片解决方案,8通道±25V模拟前端芯片,开源贴片拾取电机板
- 【MATLAB】MATLAB 仿真模拟调制系统 — VSB 系统
- Android/Linux之getevent与sendevent模拟实战(一百零八)
- 通信原理实践(四)——模拟通信系统性能分析
- 通过jquery库扩展移动端‘长按触发’事件(模拟浏览器‘长按识别二维码’功能)
- Echarts 模拟汽车速度和油量的仪表显示,两个仪表盘同图