[問題] USACO 的milk2問題 (search and insert)

看板C_and_CPP作者mingcloud (逆宇)時間15年前 (2010/05/09 15:09)推噓2(2推 0噓 9→)

留言11則, 2人參與討論串1/1

板上各位大大好第一次在這邊發文如果有什麼不對的地方請多多海涵最近在寫USACO的題目跑測資時出現了問題但是想了很久想不出來問題在哪所以想拿出來請較各位大大題目如下： Three farmers rise at 5 am each morning and head for the barn to milk three cows. The first farmer begins milking his cow at time 300 (measured in seconds after 5 am) and ends at time 1000. The second farmer begins at time 700 and ends at time 1200. The third farmer begins at time 1500 and ends at time 2100. The longest continuous time during which at least one farmer was milking a cow was 900 seconds (from 300 to 1200). The longest time no milking was done, between the beginning and the ending of all milking, was 300 seconds (1500 minus 1200). Your job is to write a program that will examine a list of beginning and ending times for N (1 <= N <= 5000) farmers milking N cows and compute (in seconds): * The longest time interval at least one cow was milked. * The longest time interval (after milking starts) during which no cows were being milked . input格式會先給總共有幾個農夫再給出各自的工作開始時間和結束時間 3 300 1000 700 1200 1500 2100 想法：我把這個問題想成一個search and insert的問題先吃進第一組農夫的時間從第二祖時間開始先跑search 去搜尋該個時間(不論是開始或是結束)所該插入的位置可以得到兩個位置(分別式 startptr , endptr) 接著對這兩個ptr去做判斷如果 startptr==endptr 且 startptr mod2==0 表示這組時間沒有跟其他任何時間重疊所以就插入這組時間插入之前先跑一個forloop把這個位子之後的time往後移 mod 2的想法來自於最後希望的排列方式會是兩兩為一interval a1 b1 a2 b2 a3 b3 (a1 a2 a3是開始時間 b1 b2 b3是結束時間) 如果startptr==endptr 且startptr mod 2 !=0 表示這組時間已經在其他的interval之中所以不做任何處置接下來為不相等的狀況表示有和其他時間重疊到(startptr!=endptr) 不相等有四種case 分別式 1.starttime 和endtime包住其他組完整的interval 2.startime 和 endtime 各自被依組interval包住所以取startime interval 得head 跟 endtime interval得tail 3.starttime包住別人 endtime 被其他interval包住 4.endtime包住別人 startime被其他interval包住以下是我的程式碼: http://nopaste.csie.org/7de62 可是現在跑出來的答案還是不對不知道想法中有哪邊有漏洞希望各位大大門可以指點一番 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.230.127.56

推

LPH66

05/09 15:14, , 1^F

05/09 15:14, 1^F

→

mingcloud

05/09 15:14, , 2^F

05/09 15:14, 2^F

→

mingcloud

05/09 15:14, , 3^F

05/09 15:14, 3^F