CodeForces - 1066B Heaters 体验还不错

B. Heaters

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 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

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 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.

分析：

题意：

给你一串序列，当数为1都能影响一段区间，求至少选取几个点才能影响全部序列。

把每一个点影响的区间记录下来，拍个序，优先选取就ok，主题有一个好做的点，就是区间长度都一样

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int N=1010;
long long n,m;
long long a[N];
struct node
{
    long long l,r;
}b[N];
bool cmp(node x,node y)
{
    if(x.l==y.l)
    {
        return x.r>=y.r;
    }
    return x.l<=y.l ;
}
int main()
{

    
    while(scanf("%lld%lld",&n,&m)!=EOF)
    {
    m--;
    int flag=0;
    long long ans=0;
    int j=0;
    for(int i=1;i<=n;i++)
    {
        flag=0;
        scanf("%d",&a[i]);  
        if(a[i]==1)
        {
          b[j].l=i-m;
          if(b[j].l<=0)b[j].l=1;
          b[j].r=i+m;
          j++; 
        }
    }
     sort(b,b+j,cmp);
     if(j==0) 
    {
        printf("-1\n");
            continue;
    }
    
    long long x=b[0].l,y=b[0].r;
    ans++;
     if(b[0].l!=1)
    {
        printf("-1\n");
            continue;
    }
    while(1)
    {
        
        int flag1=0;
        if(y>=n)
        {
            flag=1; 
            break;
        }
        int i=j-1;
        while(i>=0)
        {
         if(b[i].l>x&&b[i].l<=y+1)
         {
            //cout<<x<<" "<<y<<endl;
            ans++;
            x=b[i].l;
            y=b[i].r;
            flag1=1;
            if(y>=n)
            {
                flag=1; 
                break;
            }
         }
         i--;
        }
        if(flag1==0)
        {
            break;
        }
        
    }
    if(flag==1)
    printf("%lld\n",ans);
    else
    printf("-1\n");
    }
    return 0;
}