# codeforces 1066B（贪心）

### 题意描述

Vova’s house is an array consisting of n 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 i-th element of the array is 1 if there is a heater in the position i, otherwise the i-th element of the array is 0.

Each heater has a value r (r is the same for all heaters). This value means that the heater at the position pos can warm up all the elements in range [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=6, r=2 and heaters are at positions 2 and 5, then Vova can warm up the whole house if he switches all the heaters in the house on (then the first 3 elements will be warmed up by the first heater and the last 3 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.

### AC代码

```#include<bits/stdc++.h>
#define x first
#define y second
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<long,long> PLL;
typedef pair<char,char> PCC;
typedef long long LL;
const int N=1010;
const int M=150;
const int INF=0x3f3f3f3f;
const int MOD=998244353;
int used[N];
void solve(){
int n,r;cin>>n>>r;
for(int i=1;i<=n;i++) cin>>used[i];
int pos=1;
int ans=0;
while(pos<=n){
int idx=0;
int st=min(pos+r-1,n);
int ed=max(pos-r+1,1);
for(int i=st;i>=ed;i--){
if(used[i]){
idx=i;
break;
}
}
if(!idx){
cout<<-1<<endl;
return;
}
pos=idx+r;
ans++;
}
cout<<ans<<endl;
}
int main(){
IOS;
solve();
return 0;
}```

0 条评论

• ### Yet Another Walking Robot （Map）

There is a robot on a coordinate plane. Initially, the robot is located at the p...

• ### POJ1611 (并查集)

Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetio...

• ### B. Minimize the Permutation (贪心)

You are given a permutation of length n. Recall that the permutation is an array...

• ### P3507 [POI2010]GRA-The Minima Game

题目描述 Alice and Bob learned the minima game, which they like very much, recently....

• ### POJ--1050--To the Max（线性动规，最大子矩阵和）

To the Max Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 4...

• ### 使用 PInvoke.net Visual Studio Extension 辅助编写 Win32 函数签名

2018-07-21 14:35

• ### HOJ Recoup Traveling Expenses(最长递减子序列变形)

A person wants to travel around some places. The welfare in his company can cov...

• ### POJ 1651 Multiplication Puzzle(区间DP)

Multiplication Puzzle Time Limit: 1000MS Memory Limit: 65536K Total Sub...

• ### HDU-1011 Starship Troopers（树形dp）

Starship Troopers Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536...

• ### Codeforces Beta Round #1 A,B,C

A. Theatre Square time limit per test:1 second memory limit per test:256 megabyt...