Telefoni

Forgotten_freopen · 2021-08-08 17:34:41 · 题解

简化版题意（可忽略）

给出一个有 n 个数且里面只有 0 和 1 的数列，保证第一个数和第 n 个数都是 1，请求出至少要将多少个 0 变成 1，使得每两个相邻的 1 之间的距离均不超过 d。

解析

因为原题意是让最后一个办公桌上的电话响起，所以我们可以从最后一个电话开始向前枚举。

定义一个变量 p，表示当前已经枚举到了第 p 个办公桌，将其初始化为 n，然后每次向前枚举 d 个办公桌。如果这个办公桌（即第 p - j 个办公桌）上有电话，p 的值就变成这个办公桌的编号（即 p = \max(p - j,1)）。

q = p;//p 用来记录现在 p 的值。 
        for(j = 1; j <= d; j++){
            if(a[q - j]){//如果这个办公桌上有电话，p 就变成这个办公桌的编号。
                p = max(q - j,1);
            }
        }

如果一轮下来，p 的值没有发生变化，就说明我们需要在第 \max(p - d,1)（最优）个办公桌上放一台电话。同时，p 的值也要变成 \max(p - d,1)。

if(q == p){//如果p没有变化，就说明需要在 max(p - d,1) 处多一个电话。 
            s++;
            p = max(p - d,1);//同时，p 也变成这个刚有电话的办公桌的编号。
        }

最后，只需要在 p = 1 的时候退出循环就好了。

if(p == 1){//枚举完就退出循环。 
            break;
        }

AC code

#include<bits/stdc++.h>
using namespace std;
int n,d,i,j,s,p,q;
bool a[300005];
int main(){
    cin >> n >> d;
    for(i = 1; i <= n; i++){
        cin >> a[i];
    }
    p = n;
    for(i = 1; ; i++){
        q = p;//p 用来记录现在 p 的值。 
        for(j = 1; j <= d; j++){
            if(a[q - j]){//如果这个办公桌上有电话，p 就变成这个办公桌的编号。
                p = max(q - j,1);
            }
        }
        if(q == p){//如果p没有变化，就说明需要在 max(p - d,1) 处多一个电话。 
            s++;
            p = max(p - d,1);//同时，p 也变成这个刚有电话的办公桌的编号。
        }
        if(p == 1){//枚举完就退出循环。 
            break;
        }
    }
    cout<< s << endl;
    return 0;
}