开灯变形问题（枚举法）

约定不等于承诺〃 2023-10-05 13:39 15阅读 0赞

### 一、问题描述 ###

**一排有N盏灯。事先给定每盏灯的初始状态（开着或关着），你的任务是计算出至少要切换多少盏灯的状态（把开着的关掉，或把关着的打开），使得这N盏灯交替地打开和关闭。**

Input

输入文件中有多组测试数据，每行一组。首先是一个整数N（1<=N<=10000）表示灯的个数。然后是N个整数，表示这N盏灯的状态（1表示打开，0表示关闭）。测试数据直到文件尾。

Output

对每组测试数据输出一个至少需要切换的灯的数目，占一行。

Sample Input

9 1 0 0 1 1 1 0 1 0
    3 1 0 1

Sample Output

3
    0

### 二.问题解析 ###

本题可以采用枚举法求解：

**（1）**一共n盏灯，每个灯有2种状态，则n盏灯共有2^n种状态，分别是从000……00 到1111……11，可以枚举2^n种状态，每种状态判断一下是否是开和关交替出现的，如果不是，还要统计一下从初始状态切换到开关交替状态需要切换多少盏灯。这种枚举方法当n很大的时候，显然花费你很长时间，所以不行。

**（2）**要使n盏灯开和关交替出现，显然只有两种情况：一种要么是所有的奇数序号的灯全部为1且偶数序号的灯也为0，才能显示出开和关交替状态；另一种是所有的奇数序号的灯全部为0且偶数序号的灯也为1

才能显示出开和关交替状态；所以要分别计算这两种情况从初始状态切换到开和关交替状态分别需要切换多少盏灯。最后取两种情况下最小切换灯的数量，例如题目中第一个测试用例：

初始状态：`9 1 0 0 1 1 1 0 1 0 ，假设所有的奇数序号全为开着，偶数全为关闭着；则开和关的交替状态是1 0 1 0 1 0 1 0 1，这种情况需要至少切换的灯的数量为 6;假设所有的奇数序号全为关闭着，偶数全为开着；则开和关的交替状态是0 1 0 1 0 1 0 1 0 ，这种情况需要至少切换的灯的数量为3，所以综上两种情况取切换的灯数量最小的为3`

**（3）**从上面可以看出，两种情况需要切换的灯数量加起来6+3=9,刚好是灯的总数，所以我们只需要求其中一种情况下需要切换的灯的数量num就可以求出其中另一种情况下需要切换的灯的数量n-num,

我们通过判断当前已求的num是否大于总灯数的一半（即n/2）,如果不大于n/2,则直接输出num,如果大于n/2,则输出n-num,这种枚举方法只需求一种情况就行。

### 三.c语言源码 ###

#include<stdio.h>
    #define max 10001
    int main(){
      int a[max];
      int n,num;
    
      while(scanf("%d",&n)!=EOF){
    	  num=0;
    	  for(int i=1;i<=n;i++){
    	    scanf("%d",&a[i]);
    	  }
    
     //我这里假设奇数序号的全部为1，偶数全为0.这样才能所有的灯开闭，当然也可以偶数序号的全部为1，奇数全为0，这是两种情况
    
          for(int j=1;j<=n;j++){
    	    if(j%2==1&&a[j]==0)  num++;       //如果发现奇数序号的数为0，则修改，num+1
    	    if(j%2==0&&a[j]==1)  num++;      //如果发现偶数序号的数为1，则修改，num+1
    	  }
    
    	  if(num>n/2) printf("%d", n-num);    //如果num数目大于一半的数组，则返回另一种情况的修 改的数目n-num
    	  else
    		  printf("%d", num);  //如果num数目小于一半的数组，则直接输出num
    	  printf("\n");
      }
      
      return 0;
    }