博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Saruman's Army
阅读量:5823 次
发布时间:2019-06-18

本文共 2077 字,大约阅读时间需要 6 分钟。

Saruman's Army
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 4420   Accepted: 2285

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 310 20 2010 770 30 1 7 15 20 50-1 -1

Sample Output

24

 

 

#define _CRT_SECURE_NO_DEPRECATE#include
#include
#include
#include
#include
#define MAX 1001using namespace std;int troop[MAX];void solve(){ int r, n, res; while (cin >> r >> n){ if (r == -1 && n == -1)return; res = 0; for (int i = 0; i < n; i++)cin >> troop[i]; sort(troop, troop + n); for (int i = 0, far; i < n;){ far = troop[i]; while (i < n&&troop[i] - far <= r)i++; res++; //cout << "round:" << res << endl; far = troop[i - 1]; while (i < n&&troop[i] - far <= r)i++; } cout << res << endl; }}int main(){ solve(); //system("pause"); return 0;}

 

转载于:https://www.cnblogs.com/littlehoom/p/4198723.html

你可能感兴趣的文章
sqlserver 取取月初月末和月份间隔
查看>>
Vagrant的一个BUG - 不支持'change_host_name'
查看>>
实验二
查看>>
独立开发一个云(PaaS)的核心要素, Go, Go, Go!!!
查看>>
java的继承性
查看>>
tomcat 实例
查看>>
MyBatis使用DEMO及cache的使用心得
查看>>
网站文章如何能自动判定是抄袭?一种算法和实践架构剖析
查看>>
【OpenCV学习】滚动条
查看>>
ofo用科技引领行业进入4.0时代 用户粘性连续8个月远甩摩拜
查看>>
无法拒绝|华为618最高优惠1000元 更有梅西签名球衣奉送
查看>>
乐信Q2季报图解:调整后净利过5亿 同比增长776%
查看>>
兰州青年志愿者“中西合璧”玩快闪 温暖旅客回家路
查看>>
计划10年建10万廉价屋 新西兰政府:比想象中难
查看>>
甘肃发首版《3D打印职业教育教材》:校企合作育专才
查看>>
内蒙古2019年精准脱贫新“目标”:20个贫困旗县全部摘帽
查看>>
韩国国会议员涉嫌投机炒房 检方称已立案调查
查看>>
李娜入选国际网球名人堂 成亚洲第一人
查看>>
为找好心人抚养孩子 浙江一离婚父亲将幼童丢弃公园
查看>>
晚婚晚育 近20年巴西35岁以上孕妇增加65%
查看>>