『ACM C++』 Codeforces | 1066B - Heaters
2019-03-04 09:53:13来源：博客园 阅读 ()
今日不写日感，直接扔上今日兴趣点：
新研究称火星曾经有一个巨大的地下水系统
链接：https://mbd.baidu.com/newspage/data/landingsuper?context=%7B"nid"%3A"news_6959868648919860397"%7D&n_type=0&p_from=1
------------------------------------------------题目----------------------------------------------------------
Heaters
Vova's house is an array consisting of nn elements (yeah, this is the first problem, I think, where someone lives in the array). There are heaters in some positions of the array. The ii-th element of the array is 11 if there is a heater in the position ii, otherwise the ii-th element of the array is 00.
Each heater has a value rr (rr is the same for all heaters). This value means that the heater at the position pospos can warm up all the elements in range [pos−r+1;pos+r−1][pos−r+1;pos+r−1].
Vova likes to walk through his house while he thinks, and he hates cold positions of his house. Vova wants to switch some of his heaters on in such a way that each element of his house will be warmed up by at least one heater.
Vova's target is to warm up the whole house (all the elements of the array), i.e. if n=6n=6, r=2r=2 and heaters are at positions 22 and 55, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first 33 elements will be warmed up by the first heater and the last 33 elements will be warmed up by the second heater).
Initially, all the heaters are off.
But from the other hand, Vova didn't like to pay much for the electricity. So he wants to switch the minimum number of heaters on in such a way that each element of his house is warmed up by at least one heater.
Your task is to find this number of heaters or say that it is impossible to warm up the whole house.
Input
The first line of the input contains two integers nn and rr (1≤n,r≤10001≤n,r≤1000) — the number of elements in the array and the value of heaters.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤10≤ai≤1) — the Vova's house description.
Output
Print one integer — the minimum number of heaters needed to warm up the whole house or -1 if it is impossible to do it.
Examples
input
6 2 0 1 1 0 0 1
output
3
input
5 3 1 0 0 0 1
output
2
input
5 10 0 0 0 0 0
output
-1
input
10 3 0 0 1 1 0 1 0 0 0 1
output
3
Note
In the first example the heater at the position 22 warms up elements [1;3][1;3], the heater at the position 33 warms up elements [2,4][2,4] and the heater at the position 66 warms up elements [5;6][5;6] so the answer is 33.
In the second example the heater at the position 11 warms up elements [1;3][1;3] and the heater at the position 55 warms up elements [3;5][3;5] so the answer is 22.
In the third example there are no heaters so the answer is -1.
In the fourth example the heater at the position 33 warms up elements [1;5][1;5], the heater at the position 66 warms up elements [4;8][4;8] and the heater at the position 1010 warms up elements [8;10][8;10] so the answer is 33.
------------------------------------------------题目----------------------------------------------------------
（一） 原题大意：
有n个位置顺序排列。可以在某些位置放置灯光。假设x位置放置了一个灯光，这样位置在[x-r+1,x+r-1]范围内的所有位置都可以被灯光的光辉照亮
所有位置都想要被照亮，请问要至少多少个灯？
注：无解的话输出-1。
输入的第一行包含两个整数n和r（1≤n，r≤1000） - 位置的个数和灯光光线半径。
第二行包含n个整数a1，a2，...，（0≤ai≤1） - ai=1代表该位置可以放灯光，但不一定有必要。
最后打印一个整数 - 至少要放的灯光个数，如果不可能照亮所有位置，则为-1。
原文链接:https://www.cnblogs.com/winniy/p/10463629.html
如有疑问请与原作者联系
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换（用户自定义类类型） 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
