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

            日韩欧美亚洲综合久久影院Ds| 亚洲精品午夜国产VA久久成人| 久久精品国产99国产精品澳门 | 亚洲第一极品精品无码久久| 一本一本久久A久久综合精品| 狠狠色丁香久久婷婷综合五月| 久久se精品一区二区影院 | 精品久久久久久99人妻| 亚洲精品无码久久毛片 | 欧美日韩精品久久久免费观看| 亚洲日本久久久午夜精品| 久久99精品久久久久久hb无码| 日批日出水久久亚洲精品tv| 国产91色综合久久免费分享| 久久精品国产久精国产一老狼| 精品国产婷婷久久久| 久久久无码人妻精品无码| 久久久无码精品午夜| 国产高潮国产高潮久久久| 久久精品国产AV一区二区三区| 国産精品久久久久久久| 久久精品嫩草影院| 色8久久人人97超碰香蕉987| 亚洲国产综合久久天堂 | 久久伊人中文无码| 久久国产精品99久久久久久老狼 | 久久成人18免费网站| 久久精品国产半推半就| 色婷婷综合久久久久中文| 国产69精品久久久久久人妻精品| 热综合一本伊人久久精品| 久久久久亚洲精品男人的天堂| 久久免费精品视频| 日本免费久久久久久久网站| 久久91综合国产91久久精品| 国产精品99久久久久久人| 九九99精品久久久久久| 国产精品热久久无码av| 久久精品国产色蜜蜜麻豆 | 无码国内精品久久人妻| 亚洲精品乱码久久久久久|