『ACM C++』 Codeforces | 1066B - Heaters

来源:https://www.cnblogs.com/winniy/archive/2019/03/02/10463629.html
-Advertisement-
Play Games

今日不寫日感,直接扔上今日興趣點: 新研究稱火星曾經有一個巨大的地下水系統 鏈接:https://mbd.baidu.com/newspage/data/landingsuper?context=%7B"nid"%3A"news_6959868648919860397"%7D&n_type=0&p_ ...


今日不寫日感,直接扔上今日興趣點:

新研究稱火星曾經有一個巨大的地下水系統

鏈接: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 [posr+1;pos+r1][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 (1n,r10001≤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 (0ai10≤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。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 究竟啥才是互聯網架構“高併發” 一、什麼是高併發 高併發(High Concurrency)是互聯網分散式系統架構設計中必須考慮的因素之一,它通常是指,通過設計保證系統能夠同時並行處理很多請求。 高併發相關常用的一些指標有響應時間(Response Time),吞吐量(Throughput),每秒查 ...
  • 一、啥是數據解析 在上一篇關於爬蟲的博客里,我提到過,整個爬蟲分為四個部分,上一篇博客已經完成了前兩步,也就是我說的最難的地方,接下來這一步數據解析不是很難,但就是很煩人,但只要你有耐心,一步一步查找、排除就會提取出目標信息,這一步就相當於從接收到的龐大數據中提取出真正想要、有意義的信息,所以對於爬 ...
  • Django之路:安裝與配置 MTV Model Template View 資料庫 模版文件 業務處理 瞭解Django框架,功能齊全 一.安裝Django&Django基本配置 安裝Django pip3 django 配置Django 1.配置Django環境變數 D:\Program fil ...
  • 從生成器到協程 協程是指一個過程,這個過程與調用方協作,產出由調用方提供的值。生成器的調用方可以使用 .send(...)方法發送數據,發送的數據會成為yield表達式的值。因此,生成器可以作為協程使用。 從句法上看,生成器與協程都是包含yield關鍵字的函數。但是,在協程中,yield通常出現在表 ...
  • 對於程式員來說安全防禦,無非從兩個方面考慮,要麼前端要麼後臺。 一、首先從前端考慮過濾一些非法字元。 前端的主控js中,在<textarea> 輸入框標簽中,找到點擊發送按鈕後,追加到聊天panel前 進行過濾Input輸入內容 二、在後臺API服務解決反射型XSS漏洞 thinking:一般來說前 ...
  • 一般的程式員或許只需知道一些JAVA的語法結構,能對資料庫數據進行CRUD就可以應付了。但要成為JAVA(高級) 工程師,就要對JAVA做比較深入的研究,需要不斷學習進步,以下對高級工程師需要突破的知識點做個簡要整理 ...
  • 1、 "官網" 下載 選擇一個速度快的鏡像 推薦東軟這個 2、雙擊下載的安裝包,下一步 其中有一步是選擇Eclipse版本,SE選第一個,EE第二個。仔細審題吧。 3、配置JDK 應用、關閉 4、測試:寫個Hello World運行 1)New Project 寫個工程名 finish 2)在src ...
  • 當都為正數時,即1+2+3+...+99,如上,很簡單; 其實,計算正負相間的式子也很簡單,只需要加上一個標記正負號的變數乘到計數器上即可。 用一個布爾型變數來記錄執行加法還是減法,也能達到同樣的效果(這裡額外增加一個要求,就是剔除某個數後,保持正負相間的累加) 這樣,得到的就是1-2+3-4... ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...