找到打开所有灯泡的最少开关数量 [英] FInd the minimum number of switches to turn on all bulbs

问题描述

我试图理解给定的问题 这里 及其解决方案:

I am trying to understand the problem given here and its solution:

问题说明:

N 个灯泡由一根电线连接.每个灯泡都有一个与之关联的开关，但是由于接线错误，开关也会改变当前灯泡右侧的所有灯泡的状态.给定所有灯泡的初始状态，找出您必须按下才能打开所有灯泡的最少开关数量.您可以多次按下同一个开关.

N light bulbs are connected by a wire. Each bulb has a switch associated with it, however due to faulty wiring, a switch also changes the state of all the bulbs to the right of current bulb. Given an initial state of all bulbs, find the minimum number of switches you have to press to turn on all the bulbs. You can press the same switch multiple times.

注意:0代表灯泡关闭，1代表灯泡开启.

Note : 0 represents the bulb is off and 1 represents the bulb is on.

Example:

Input : [0 1 0 1]
Return : 4

Explanation :

press switch 0 : [1 0 1 0]
press switch 1 : [1 1 0 1]
press switch 2 : [1 1 1 0]
press switch 3 : [1 1 1 1]

给出的答案之一是:

int solve(int A[], int N) {

    int state= 0, ans = 0;
    for (int i = 0; i < N;i++) {
        if (A[i] == state) {
            ans++;
            state = 1 - state;
        }
    }

    return ans;
}

我似乎无法理解 if 语句如何做正确的事情.

I can't seem to wrap my head around how the if statement does the correct thing.

推荐答案

每当我们拨动开关时，我们会将所有开关向右拨动，因此如果我们现在搜索 0(off switch)，我们需要搜索 1(on switch) 因为我们已经把所有的开关都向右翻转了，让我们看一个例子:0 1 1 0，现在初始状态= 0，当我们遇到第一个灯泡时，我们翻转所有开关，即 1 0 0 1 但在数组中的值仍然是 0 1 1 0，所以我们需要能够认识到由于前一次翻转，第二个索引处的灯泡关闭，因此我们将状态更改为 1 - 状态，这使得我们正在寻找的状态为 1，类似地翻转开关会更改我们下一个状态的标准会搜索.

Whenever we flip a switch we flip all the switches towards the right, so if we were searching for 0(off switch) now we need to search for 1(on switch) because we have flipped all the switches towards the right, lets look at an example : 0 1 1 0, now initially state = 0, when we encounter the first bulb we flip all the switches, i.e 1 0 0 1 but in the array the values are still 0 1 1 0, so we need to be able to recognize that the bulb at the second index is switched off due to the previous flip, so we change the state to 1 - state, which makes the state that we are looking for is 1, similarly flipping the switches changes the criteria of the next state that we will search.

我在下面写了一个代码片段，这样会更容易理解

I have written a code snippet below, that would be more understandable

bool flipped = false;
int ans = 0;
for(int i = 0;i < N;i++){
    if(flipped == false){
        if(A[i] == 0){
            ans++;
            flipped = true;
        }
    }else if(flipped == true){
        if(A[i] == 1){
            ans++;
            flipped = false;
        }
    }
}

这里我使用了翻转变量，它告诉灯泡是否已经翻转，如果它们已经翻转，那么我们将搜索 1(开关上)，因为实际上它们是 0(关闭)，因为之前的翻转.

Here i am using the flipped variable that tells whether the bulbs have been flipped or not if they have been flipped then we will search for 1(on switches), because in reality they are 0(off) because of previous flip.

这篇关于找到打开所有灯泡的最少开关数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！