[COCI2016-2017#6] Telefoni题解

lanretE · 2021-08-09 13:06:38 · 题解

一道简单的贪心题。

大致思路：如果空隙（连续 0 的长度）超过 d 则增加一台电话，不然不加。

实现：

定义 blk 记录当前空隙长度，读到 0 则加 1，读到 1 说明空隙结束，需要增加的电话数量即为 \left\lfloor\dfrac{blk}{d}\right\rfloor。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,d;
    cin>>n>>d;
    int blk=0,ans=0;
    while(n--){
        bool x; cin>>x;
        if(x){
            ans+=blk/d;
            blk=0;
        }
        else blk++;
    } 
    cout<<ans<<endl;
    return 0;
}