• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            ZOJ1622 SWITCH解題報告

            Posted on 2010-09-20 09:31 李東亮 閱讀(332) 評論(0)  編輯 收藏 引用

             

            SWITCH

            題目描述如下:

            There are N lights in a line. Given the states (on/off) of the lights, your task is to determine at least how many lights should be switched (from on to off, or from off to on), in order to make the lights on and off alternatively.
            Input
            One line for each testcase.
            The integer N (1 <= N <= 10000) comes first and is followed by N integers representing the states of the lights ("1" for on and "0" for off).
            Process to the end-of-file.
            Output
            For each testcase output a line consists of only the least times of switches.
            Sample Input
            3 1 1 1
            3 1 0 1
            Sample Output
            1
            0

            分析:該題看似簡單但卻隱藏著陷阱,題目要求尋找的是最少的切換數,故從第二盞燈開始判斷處理得出的結論是不一定正確的。通過分析可以發現該題其實只存在兩種情況:奇數位置的燈開著或者偶數位置的燈開著。這樣可以直觀的處理該題:取奇數位置燈開著需要切換燈狀態數與偶數位置燈開著需切換燈狀態數的較小值。這樣的話需要掃描兩邊燈的狀態數組,開銷較大。進一步分析,設a為奇數位置的燈開著需要切換的燈數,b為偶數位置燈開著需要切換的燈數。其實a+b=n。這樣本題就只需要掃描一遍數組,且進一步優化后存儲燈狀態的數組也可以省了。具體代碼如下:

             

             1#include <stdio.h>
             2#include <stdlib.h>
             3
             4int main(void)
             5{
             6    int n;
             7    int prev;
             8    int tmp;
             9    int cnt;
            10    int a;
            11    while (scanf("%d"&n) == 1)
            12    {
            13        prev = -1;
            14        cnt = 0;
            15        a = n;
            16        while (n--)
            17        {
            18            scanf("%d"&tmp);
            19            if (tmp == prev)
            20            {
            21                if (tmp == 0)
            22                {
            23                    prev = 1;
            24                }

            25                else
            26                {
            27                    prev = 0;
            28                }

            29                ++cnt;
            30                continue;
            31            }

            32            prev = tmp;
            33        }

            34        if (cnt > a/2)
            35            cnt = a-cnt;
            36        printf("%d\n", cnt);
            37    }

            38    return 0;
            39}

            posts - 12, comments - 1, trackbacks - 0, articles - 1

            Copyright © 李東亮

            97久久久久人妻精品专区| 久久se精品一区精品二区国产| 久久夜色撩人精品国产| 久久婷婷色香五月综合激情 | 2022年国产精品久久久久| 97精品国产91久久久久久| 精品久久久久久无码人妻热| 久久99九九国产免费看小说| 国产精品久久久福利| 婷婷久久综合| 国产成人无码精品久久久免费| 日韩亚洲国产综合久久久| av国内精品久久久久影院| 国产精品综合久久第一页| 亚洲午夜久久久久久久久久| 国产亚洲色婷婷久久99精品91| 久久婷婷五月综合97色直播| 久久99精品久久久久久久不卡| 久久亚洲视频| 久久久国产精品福利免费 | 国产成人香蕉久久久久| 欧美黑人又粗又大久久久| 久久影视综合亚洲| 精品久久一区二区| 无码国产69精品久久久久网站| 久久精品中文字幕一区| 久久国产精品99精品国产| 久久久久久久精品妇女99| 久久强奷乱码老熟女网站| 国产免费久久精品99久久| 91久久精品国产91性色也| 91久久精品91久久性色| 久久久久久无码Av成人影院| 久久天天躁夜夜躁狠狠| 久久这里有精品视频| 久久久久久国产精品无码下载| 精品国产一区二区三区久久| 91精品国产综合久久四虎久久无码一级| 久久精品国产亚洲AV无码娇色| 色综合久久久久久久久五月| 亚洲AV成人无码久久精品老人|