一、問(wèn)題描述

一排有N盞燈。事先給定每盞燈的初始狀態(tài)（開(kāi)著或關(guān)著），你的任務(wù)是計(jì)算出至少要切換多少盞燈的狀態(tài)（把開(kāi)著的關(guān)掉，或把關(guān)著的打開(kāi)），使得這N盞燈交替地打開(kāi)和關(guān)閉。

Input

輸入文件中有多組測(cè)試數(shù)據(jù)，每行一組。首先是一個(gè)整數(shù)N（1<=N<=10000）表示燈的個(gè)數(shù)。然后是N個(gè)整數(shù)，表示這N盞燈的狀態(tài)（1表示打開(kāi)，0表示關(guān)閉）。測(cè)試數(shù)據(jù)直到文件尾。

Output

對(duì)每組測(cè)試數(shù)據(jù)輸出一個(gè)至少需要切換的燈的數(shù)目，占一行。

Sample Input

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

Sample Output

3 0

二.問(wèn)題解析

本題可以采用枚舉法求解：

（1）一共n盞燈，每個(gè)燈有2種狀態(tài)，則n盞燈共有2^n種狀態(tài)，分別是從000……00 到1111……11，可以枚舉2^n種狀態(tài)，每種狀態(tài)判斷一下是否是開(kāi)和關(guān)交替出現(xiàn)的，如果不是，還要統(tǒng)計(jì)一下從初始狀態(tài)切換到開(kāi)關(guān)交替狀態(tài)需要切換多少盞燈。這種枚舉方法當(dāng)n很大的時(shí)候，顯然花費(fèi)你很長(zhǎng)時(shí)間，所以不行。

（2）要使n盞燈開(kāi)和關(guān)交替出現(xiàn)，顯然只有兩種情況：一種要么是所有的奇數(shù)序號(hào)的燈全部為1且偶數(shù)序號(hào)的燈也為0，才能顯示出開(kāi)和關(guān)交替狀態(tài)；另一種是所有的奇數(shù)序號(hào)的燈全部為0且偶數(shù)序號(hào)的燈也為1

才能顯示出開(kāi)和關(guān)交替狀態(tài)；所以要分別計(jì)算這兩種情況從初始狀態(tài)切換到開(kāi)和關(guān)交替狀態(tài)分別需要切換多少盞燈。最后取兩種情況下最小切換燈的數(shù)量，例如題目中第一個(gè)測(cè)試用例：

初始狀態(tài)：9 1 0 0 1 1 1 0 1 0? ，假設(shè)所有的奇數(shù)序號(hào)全為開(kāi)著，偶數(shù)全為關(guān)閉著；則開(kāi)和關(guān)的交替狀態(tài)是1 0 1 0 1 0 1 0 1，這種情況需要至少切換的燈的數(shù)量為 6;假設(shè)所有的奇數(shù)序號(hào)全為關(guān)閉著，偶數(shù)全為開(kāi)著；則開(kāi)和關(guān)的交替狀態(tài)是0 1 0 1 0 1 0 1?0?，這種情況需要至少切換的燈的數(shù)量為3，所以綜上兩種情況取切換的燈數(shù)量最小的為3

（3）從上面可以看出，兩種情況需要切換的燈數(shù)量加起來(lái)6+3=9,剛好是燈的總數(shù)，所以我們只需要求其中一種情況下需要切換的燈的數(shù)量num就可以求出其中另一種情況下需要切換的燈的數(shù)量n-num,

我們通過(guò)判斷當(dāng)前已求的num是否大于總燈數(shù)的一半（即n/2）,如果不大于n/2,則直接輸出num,如果大于n/2,則輸出n-num,這種枚舉方法只需求一種情況就行。

三.c語(yǔ)言源碼

#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]);}//我這里假設(shè)奇數(shù)序號(hào)的全部為1，偶數(shù)全為0.這樣才能所有的燈開(kāi)閉，當(dāng)然也可以偶數(shù)序號(hào)的全部為1，奇數(shù)全為0，這是兩種情況for(int j=1;j<=n;j++){if(j%2==1&&a[j]==0) num++; //如果發(fā)現(xiàn)奇數(shù)序號(hào)的數(shù)為0，則修改，num+1if(j%2==0&&a[j]==1) num++; //如果發(fā)現(xiàn)偶數(shù)序號(hào)的數(shù)為1，則修改，num+1}if(num>n/2) printf("%d", n-num); //如果num數(shù)目大于一半的數(shù)組，則返回另一種情況的修 改的數(shù)目n-numelseprintf("%d", num); //如果num數(shù)目小于一半的數(shù)組，則直接輸出numprintf("\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的开灯变形问题（枚举法）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。