貪心算法 1050 2037

1050 Moving Tables
題目大意:
題意:在一個長走廊里搬桌子吴超,走廊的兩側都是房間,把桌子從一個房間搬到另外一個房間杯巨,走廊的寬度只能允許一個桌子通過每聪,每次搬桌子需要10分鐘(每一次允許再不交叉的走廊中同時搬桌子),問最少多長時間搬完疲眷。
思路:
不需要研究每次的前后房間號碼禾蚕,而可以簡單地每次都根據(jù)房間號碼在相應的數(shù)組內(nèi)做出累加,得到的最大數(shù)目即為最長的時間狂丝。
如圖:有四個桌子要搬:


重疊累加后的效果如圖:


最大的參數(shù)是3换淆,那么也就是說最大的時間是3*10。
依次類推几颜,只要得到1~200單位的每一個使用次數(shù)便可:

#include <stdio.h>
#include <string.h>
void main()
{
    int A[201];
    int i,j,k,n,m;
    int a,b;
    scanf("%d",&n);
    while (n--)
    {
        memset(A,0,sizeof (A));
        scanf("%d",&m);
        while (m--)
        {
            scanf("%d%d",&a,&b);
            if (a>b)
            {
                k=a;a=b;b=k;
            }
            if (a%2==1)
                a=(a+1)/2;
            else
                a=a/2;
            if (b%2==1)
                b=(b+1)/2;
            else
                b=b/2;
            for (i=a;i<=b;i++)
                A[i]++;
        }
        int max=A[0];
        for (i=1;i<200;i++)
        {
            if(A[i]>max)
                max=A[i];
        }
        printf ("%d\n",max*10);
    }
}

2037
今年暑假不AC
已知每個節(jié)目的開始時間和結束時間倍试,求解每天能看到的最多電視節(jié)目個數(shù):求最多個數(shù),那么就是取盡量多節(jié)目時間短的蛋哭,且在空閑的時間范圍內(nèi)選擇县习。而方法則在于在已知當前的時間的情況下,找出最短結束時間的節(jié)目具壮,該節(jié)目的結束時間可以更新為當前時間准颓,繼續(xù)尋找。

#include <stdio.h>
#include <string.h>
void main()
{
    int A[201];
    int i,j,k,n,m;
    int a,b;
    scanf("%d",&n);
    while (n--)
    {
        memset(A,0,sizeof (A));
        scanf("%d",&m);
        while (m--)
        {
            scanf("%d%d",&a,&b);
            if (a>b)
            {
                k=a;a=b;b=k;
            }
            if (a%2==1)
                a=(a+1)/2;
            else
                a=a/2;
            if (b%2==1)
                b=(b+1)/2;
            else
                b=b/2;
            for (i=a;i<=b;i++)
                A[i]++;
        }
        int max=A[0];
        for (i=1;i<200;i++)
        {
            if(A[i]>max)
                max=A[i];
        }
        printf ("%d\n",max*10);
    }
}
最后編輯于
?著作權歸作者所有,轉載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末棺妓,一起剝皮案震驚了整個濱河市攘已,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌怜跑,老刑警劉巖样勃,帶你破解...
    沈念sama閱讀 217,907評論 6 506
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異性芬,居然都是意外死亡峡眶,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,987評論 3 395
  • 文/潘曉璐 我一進店門植锉,熙熙樓的掌柜王于貴愁眉苦臉地迎上來辫樱,“玉大人,你說我怎么就攤上這事俊庇∈ㄊ睿” “怎么了?”我有些...
    開封第一講書人閱讀 164,298評論 0 354
  • 文/不壞的土叔 我叫張陵辉饱,是天一觀的道長搬男。 經(jīng)常有香客問我,道長彭沼,這世上最難降的妖魔是什么缔逛? 我笑而不...
    開封第一講書人閱讀 58,586評論 1 293
  • 正文 為了忘掉前任,我火速辦了婚禮,結果婚禮上褐奴,老公的妹妹穿的比我還像新娘按脚。我一直安慰自己,他們只是感情好歉糜,可當我...
    茶點故事閱讀 67,633評論 6 392
  • 文/花漫 我一把揭開白布乘寒。 她就那樣靜靜地躺著,像睡著了一般匪补。 火紅的嫁衣襯著肌膚如雪伞辛。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 51,488評論 1 302
  • 那天夯缺,我揣著相機與錄音蚤氏,去河邊找鬼。 笑死踊兜,一個胖子當著我的面吹牛竿滨,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播捏境,決...
    沈念sama閱讀 40,275評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼于游,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了垫言?” 一聲冷哼從身側響起贰剥,我...
    開封第一講書人閱讀 39,176評論 0 276
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎筷频,沒想到半個月后蚌成,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,619評論 1 314
  • 正文 獨居荒郊野嶺守林人離奇死亡凛捏,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,819評論 3 336
  • 正文 我和宋清朗相戀三年担忧,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片坯癣。...
    茶點故事閱讀 39,932評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡瓶盛,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出示罗,到底是詐尸還是另有隱情蓬网,我是刑警寧澤,帶...
    沈念sama閱讀 35,655評論 5 346
  • 正文 年R本政府宣布鹉勒,位于F島的核電站,受9級特大地震影響吵取,放射性物質(zhì)發(fā)生泄漏禽额。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,265評論 3 329
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望脯倒。 院中可真熱鬧实辑,春花似錦、人聲如沸藻丢。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,871評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽悠反。三九已至残黑,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間斋否,已是汗流浹背梨水。 一陣腳步聲響...
    開封第一講書人閱讀 32,994評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留茵臭,地道東北人疫诽。 一個月前我還...
    沈念sama閱讀 48,095評論 3 370
  • 正文 我出身青樓,卻偏偏與公主長得像旦委,于是被迫代替她去往敵國和親奇徒。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 44,884評論 2 354

推薦閱讀更多精彩內(nèi)容