数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中计算将数组所有值设置为1所需的最少右翻转次数
我们得到一个由 0 和 1 组成的数组，表示顺序连接在同一条电线上的灯泡的状态。0 表示灯泡关闭，1 表示灯泡打开。对于这样的 N 个灯泡序列，如果按下灯泡的开关，则右侧的所有灯泡（从第 i+1 个到第 n 个）都会改变其先前状态，从打开变为关闭，或从关闭变为打开。
对于给定所有灯泡的状态，目标是找到最少需要按动的开关次数才能将所有灯泡都打开。[同一个开关可以按任意次数]。这与翻转数组中右侧索引值的状态以将它们都设置为 1 相同。
输入
Bulbs[]= { 1,0,1,0 }输出
Minimum right flips: 3
解释
原始状态 1010
Press switch 2:- 1:101 flip count=1 Press switch 3:- 11:10 flip count=2 Press switch 4:- 111:1 flip count=3
输入
Bulbs[]= { 1,0,0,0 }输出
Minimum right flips: 1
解释
Original state 1000 Press switch 2:- 1:111 flip count=1
右侧所有灯泡都打开。
下面程序中使用的方案如下
整数存储 N 个灯泡的状态。
函数 minFlips(int arr[],int n) 以数组及其长度 n 为输入，并返回将数组值设置为 1（将所有关闭的灯泡打开）所需的最少右翻转次数。
变量 count 用于存储翻转次数，初始值为 0。
数组 switch[] 用于存储与第 i 个灯泡对应的所有开关的初始状态。所有开关都关闭 (switch[]={0}.)
从 i=0 到 n 开始，我们执行以下操作：
如果灯泡打开且开关关闭，则不做任何操作（增加 i）
如果灯泡关闭且开关打开，则不做任何操作（增加 i），因为关闭开关不会改变灯泡的状态
如果灯泡关闭且开关关闭，则增加计数并翻转右侧所有灯泡的状态。（while 循环）
for 循环结束后，返回 'count' 中的结果作为已执行的翻转次数。
- 返回 count。
示例
// C++ program to find minimum number of move-to-front
// moves to arrange items in sorted order.
#include <bits/stdc++.h>
using namespace std;
// Calculate minimum number of moves to arrange array
// in increasing order.
int minFlips(int arr[], int n){
int count = 0;
int swich[n] = {0}; //Initially we don't flip the states, so flip is false
for(int i=0;i<n;i++){
if(arr[i]==1 && swich[i]==0)
i++;
if(arr[i]==0 && swich[i]==1)
i++;
if(arr[i]==0 && swich[i]==0){
count++;
int j=i;
while(j<n){
if(arr[j]==0)
arr[j++]=1;
else
arr[j++]=0;
}
}
}
return count;
}
int main(){
int Arr[] = {0,1,0,1};
int N = 4;
cout <<”Minimum right flips to set all values in an array:"<<
minFlips(Arr, N);
return 0;
}输出
Minimum right flips to set all values in an array: 4
更新于：2020年7月28日
201 次浏览
广告