• <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 © 李東亮

            国内精品伊人久久久影院| 国产精品久久久久久| 蜜桃麻豆www久久国产精品| 亚洲成av人片不卡无码久久 | 久久人人爽人人爽人人AV| 亚洲AV成人无码久久精品老人 | 99久久99久久久精品齐齐| 亚洲国产精品一区二区久久| 亚洲午夜久久久| 人妻无码αv中文字幕久久| 99久久国产综合精品成人影院 | 国产叼嘿久久精品久久| 精品人妻伦九区久久AAA片69| 久久精品国产久精国产| 久久国产劲爆AV内射—百度| 国产成人精品综合久久久| 久久亚洲AV成人无码电影| 一本久久综合亚洲鲁鲁五月天| 久久精品亚洲一区二区三区浴池| 久久综合久久鬼色| 9999国产精品欧美久久久久久| 亚洲综合熟女久久久30p| AA级片免费看视频久久| 欧美丰满熟妇BBB久久久| 一本色道久久综合狠狠躁篇| 国内精品久久久久影院网站| 99久久无码一区人妻a黑| 麻豆AV一区二区三区久久| 波多野结衣久久精品| 亚洲国产精品狼友中文久久久 | 国产精品一久久香蕉产线看| 久久婷婷五月综合国产尤物app| 久久免费99精品国产自在现线| 国内精品久久久久久久亚洲 | 国产精品久久久久久影院| 日产精品99久久久久久| 日韩精品久久久肉伦网站| 欧美午夜精品久久久久免费视 | 久久只有这精品99| 久久精品久久久久观看99水蜜桃| 亚洲精品国产自在久久|