https://codeforces.com/contest/1066/problem/B
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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 pospos 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.
Input
The first line of the input contains two integers n and r (1≤n,r≤1000) — the number of elements in the array and the value of heaters.
The second line contains nn integers a1,a2,…,an (0≤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
Copy
6 2 0 1 1 0 0 1
output
Copy
3
input
Copy
5 3 1 0 0 0 1
output
Copy
2
input
Copy
5 10 0 0 0 0 0
output
Copy
-1
input
Copy
10 3 0 0 1 1 0 1 0 0 0 1
output
Copy
3
Note
In the first example the heater at the position 2 warms up elements [1;3], the heater at the position 3 warms up elements [2,4] and the heater at the position 6 warms up elements [5;6] so the answer is 3.
In the second example the heater at the position 1 warms up elements [1;3] and the heater at the position 5 warms up elements [3;5] so the answer is 2.
In the third example there are no heaters so the answer is -1.
In the fourth example the heater at the position 3 warms up elements [1;5], the heater at the position 6 warms up elements [4;8] and the heater at the position 10 warms up elements [8;10] so the answer is 3.
C++版本一
/*
*@Author:STZG
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
using namespace std;
typedef long long ll;
const int N=10000;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m;
int r,a[N];
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
scanf("%d%d",&n,&r);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int ans=0;
int last=0;
while(last<n){
int pos=0;
for(int i=n;i>max(0,last-r+1);i--){
if(a[i]==1&&i-r<=last){
pos=i;
break;
}
}
if(pos==0){
cout << -1 << endl;
return 0;
}
ans++;
last=pos+r-1;
}
cout << ans << endl;
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
Let's solve this problem greedily. Let lastlast be the last position from the left covered by at least one heater. Initially, lastlast equals -1. While last<n−1, lets repeat the following process: firstly, we have to find the rightmost heater in range (max(−1,last−r+1);last+r]. It can be done in time O(n) because of given constrains or in O(1) using precalculated prefix values for each ii in range [0;n−1]. If there is no such heater then the answer is -1, otherwise let's set last:=pos+r−1, increase the answer by 1 and repeat the process if last<n−1.
#include <bits/stdc++.h>
using namespace std;
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int n, r;
cin >> n >> r;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
int last = -1;
while (last < n - 1) {
int pos = -1;
for (int i = n - 1; i > max(-1, last - r + 1); --i) {
if (a[i] == 1 && i - r <= last) {
pos = i;
break;
}
}
if (pos == -1) {
cout << -1 << "\n";
return 0;
}
++ans;
last = pos + r - 1;
}
cout << ans << "\n";
return 0;
} C++版本三
There is another one solution to this problem. Assume that the initial answer equals to the total number of heaters. Let's calculate an array cnt of length n, where cnti means the number of heaters covering the i-th element. It can be done in O(n2). This array will mean that we are switch all the heaters on and we know for each element the number of heaters covers this element. Now if for at least i∈[0,n−1] holds cnti=0 then the answer is -1. Otherwise let's switch useless heaters off. Let's iterate over all heaters from left to right. Let the current heater have position i. We need to check if it is useless or not. Let's iterate in range [max(0,i−r+1),min(n−1,i+r−1)]and check if there is at least one element j in this segment such that cntj=1. If there is then the current heater is not useless and we cannot switch it off. Otherwise we can decrease the answer by 1, switch this heater off (decrease cntjcntj for all j in range [max(0,i−r+1),min(n−1,i+r−1)]) and continue the process.
#include <vector>
#include <iostream>
#define forn(i,n) for (int i=0; i<int(n); i++)
using namespace std;
const int N = 2e5;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, r; cin >> n >> r;
vector<int> a(n);
vector<int> cnt(n);
int ans = 0;
forn(i, n)
{
cin >> a[i];
if (a[i])ans++;
if (a[i])
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
cnt[j]++;
}
forn(i, n)
if (!cnt[i])
{
cout << -1;
return 0;
}
forn(i, n)
{
bool fl = true;
if (a[i])
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
if (cnt[j] == 1)
{
fl = false;
break;
}
if (fl && a[i])
{
ans--;
for (int j = max(0, i - r + 1); j < min(n, i + r); ++j)
cnt[j]--;
}
}
cout << ans;
}
京公网安备 11010502036488号