E-tutor [程式設計][C_AR186-易] 道路修補

簡介

題目來源：e-tutor平台
[C_AR186-易] 道路修補

道路修補，每筆測資都給我們不只一段修補路段，每段路段皆不同地方，甚至還有重複修補的地方，而題目需要我們幫他找出總共有多少修補路段，而且不能計算到重複的區域，那我們該怎麼處理那麼多不同的道路修補路段呢？

讓我們先了解題目內容

問題描述：

 因為有民眾投訴道路坑坑窪窪的，容易發生意外，考量到用路人的安全，政府決定對該道路進行修補。但基於成本考量，沒辦法將道路從頭到尾整修一遍，於是派出數支調查隊針對整條道路進行評估，再根據各隊評估結果計算出需進行修補的長度。舉例來說，現在有 3 個評估結果，分別為：(1) 3 到 5 公里處 (2) 6 到 13 公里處 (3) 10 到 14 公里處，則最後需要修補路段為 3 到 5 公里處以及 6 到 14 公里處，共計 10 公里的長度。現在請你寫個程式，根據每個評估結果，計算出需要修補的道路總長度。
Input：

 第一行會有一個整數代表測資筆數。每筆測資第一行有一個整數 n 表示有 n 個評估結果 (1  ≤ n  ≤ 1000)。接下來有 n 行，每行有兩個整數 s 、 e ，表示在該評估結果中需要修補的路段，其中 0 ≤ s < e  ≤ 10000 ，數值間以一個空白隔開。

Output：

 每筆測資輸出需要修補的道路總長度於一行。

範例：


解題想法：

把整條路段想像成一塊白色有格子的長方形，只要有修補的路段，就把修補路段的格子塗顏色，最後再去算有幾個格子有塗顏色。

例子：

※只要修補過就塗顏色，就可以解決重複修部部分會混亂的問題

第一步、要先處理輸入，宣告題目所需的條件

1. test 為測資筆數

2. number 為評估後需要修幾段路

3. ans 為最後要計算修補長度為多少

4. road 陣列為題目限制最大路段，全部預設0

輸入測資筆數、評估後修幾段路



第二步、設定評估後修幾段路的迴圈


迴圈：使用第一步輸入的 number 定為限制迴圈的變數

第三步、輸入路段的頭尾，並且塗顏色


宣告 2 個變數，begin 為修補路段的起頭，end 為修補路段的結尾

迴圈：起始值設為 begin，限制在 end，並且在修補範圍內的值都加一

※只要修補過的值都加一，代表塗顏色

第四步、搜尋所有路段，並且輸出答案


設定一個迴圈，從頭搜尋到尾

只要陣列數字不為 0 的，代表有塗過顏色

並且使用一開始所設的變數 ans 記錄下來

最後在輸出 ans 就完成了！

完整程式碼如下



留言

張貼留言

這個網誌中的熱門文章

E-tutor [程式設計][C_AR183-易] 數字跑馬燈

圖片
簡介 題目來源：e-tutor平台 [C_AR183-易] 數字跑馬燈 數字跑馬燈，這題在輸入資料與如何處理資料這部分比較麻煩，讀進字串後還要切割，甚至還需要把字串轉整數，需要多個步驟。 讓我們先了解題目內容 問題描述： 請讀入二行資料，第一行是一串空白隔開的數字 ( 個數 N <= 20 )，假設這是要顯示的跑馬燈，第二行是一串讓跑馬燈資訊左右轉動的命令，可以指定這一串數字向左或者向右轉的次數，當一個數字從第一個位置向左轉出時，會移動到最後一個數字，反之亦然，一個數字從最後一個位置向右轉出時，會移動到第一個數字。下面例子說明跑馬燈轉動的過程：假設讀入的一串數字如下： 20 -5 -18 6 18 22 5 7 12 51 19 讀入的轉動命令為 L 5 R 13 R 2 L 7，L 表示向左移動，R 表示向右移動，所以 L 5 表示向左移動 5 個位置，R 13 表示向右移動 13 個位置等，則這些命令依序轉動過程如下： L 5 → 22 5 7 12 51 19 20 -5 -18 6 18 R 13 → 6 18 22 5 7 12 51 19 20 -5 -18 R 2 → -5 -18 6 18 22 5 7 12 51 19 20 L 7 → 12 51 19 20 -5 -18 6 18 22 5 7 最後一行即是全部轉動完畢之後，要輸出的結果。 Input： 輸入資料有兩行，第一行是由空白隔開的一串數字 ( 最多 20 個 )，第二行是一串左轉或右轉的命令，命令之間由空白字元隔開，每個命令包含一個 L 或 R 字元 ( 皆為大寫字元 )，接著一個整數 S ( S >= 0 ) ，表示往左或者往右轉動 S 個位置。最多 25 個命令。 Output： 輸出該串數字經過這一連串的轉動命令之後的結果。 範例： 解題想法： 先處理輸入資料，把輸入的數字先存起來，再用兩個陣列儲存命令，一個是只有經過切割字串，另一個則是切割完後轉整數，資料分開後再去計算所有的左轉和右轉互相抵銷，到底該往哪個方向移動位置，接著不要去更動到原本的數字陣列，使用不同的輸出方式輸出答案。 第一步、處理題目所需的輸入格式 1.使用 vector 功能建立二個一維的 字串 陣列，分別為...
閱讀完整內容

E-tutor [程式設計][C_CH10-中] The 3n + 1 problem

圖片
簡介 題目來源：e-tutor平台 [C_CH10-中] The 3n + 1 problem The 3n+1 proble，看到題目時，第一個想法就是這題怎麼那麼佛心，題目的演算法直接給，只剩下直接幫題目所需轉成程式碼，結果仔細一看才發現案情並不單純，這題需要使用到多個判斷式與迴圈。 讓我們先了解題目內容 問題描述： 考慮以下演算法： 1.輸入 n 2.印出 n 3.如果 n = 1 結束 4.如果 n 是奇數，那麼 n = 3 * n + 1 5.否則 n = n / 2 6. GOTO 2 例如輸入 22，得到的數列：22  11  34  17  52  26  13  40  20  10  5  16  8  4  2  1 據推測此演算法對任何整數而言會終止 ( 當列印出 1 的時候 )。雖然此演算法很簡單，但以上的推測是否真實卻無法知道。然而對所有的 n ( 0 < n < 1,000,000 ) 來說，以上的推測已經被驗證是正確的。 給一個輸入 n，透過以上的演算法我們可以得到一個數列 ( 1 作為結尾 )。此數列的長度稱為 n 的 cycle-length。上面提到的例子，22 的 cycle-length 為 16。 問題來了，對任 2 個整數 i、j，我們想要知道介於 i、j ( 包含 i、j ) 之間的數所產生的數列中最大的 cycle-length 是多少。 Input： 輸入可能包含了好幾列測試資料，每一列有一對整數資料 i、j。0 < i，j < 1,000,000。 Output： 對每一對輸入 i、j 你應該要輸出 i、j 和介於 i、j 之間的數所產生的數列中最大的 cycle-length。 範例： 解題想法： 1.先判斷輸入的兩個數字大小，才能得知迴圈起始與終點該用哪個數字 2.設定輸入兩個數字的範圍迴圈 3.範圍內的數字都要經過一個計算 cycle-length 的無窮迴圈 4.無窮迴圈內設定題目提供演算法 5.把每個數字的 cycle-length...
閱讀完整內容

E-tutor [程式設計][C_AR182-中] 翻轉吧陣列

圖片
簡介 題目來源：e-tutor平台 [C_AR182-中] 翻轉吧陣列 翻轉吧陣列，先儲存資料後，經題目的命令，做出三種不同的二維陣列翻轉，做完這題可以使我們對陣列更加的了解 讓我們先了解題目內容 問題描述： 假設一個 N * N 的陣列 ( N <= 20 )，每個位置從左到右，從上到下，依序填入 1 ~ N ²  的數字，假設 N = 4，陣列的初始狀態如圖所示。接著，這裡有三種翻轉動作，分別是水平、垂直與對角翻轉，從初始狀態分別進行這三種翻轉動作後對應的結果分別如圖所示：   請撰寫一個程式，可以先讀取一個正整數 N，接著讀入一串由 H V D 所組成的翻轉字串，接著輸出初始狀態經過一連串翻轉後的結果。 Input： 輸入資料有兩行，第一行是陣列大小 N ( N <= 20 )，第二行是一個由 H V D 所組成的字串，長度 <= 20。 Output： 輸出初始狀態經過指定之一連串翻轉動作後的結果。 範例： 解題想法： 先把題目所需的方陣中數字填進去，依照命令分開寫不同的迴圈來翻轉矩陣，並且每次翻轉完取代原本的陣列，最後再輸出答案。 第一步、處理題目所需的輸入格式 1.宣告題目所需的陣列大小，number 2.宣告整數 count 等於 1，這個計數器後面會派上用場 3.宣告題目需讀入的翻轉指令字串 s 4.輸入整數 number 和字串 s ※輸入 number 後，再輸入字串 s 前要先加入 cin.ignore(1000,'\');     避免輸入完數字後按 enter，程式會誤以為 enter 就是字串 s 5.使用 vector 功能建立一個用來儲存方陣的二維整數陣列，OriginalArray 第二步、依測試資料提供的陣列大小，把數字放進二維陣列 題目並沒有給我們整個二維陣列裡的值 每次陣列的大小也不一定 因此陣列裡的值只能有我們自己放進去 1.設置一個迴圈為陣列中的列 2.迴圈內宣告一個整數陣列 buf1，為放數字用 3.迴圈內設置第二個迴圈為陣列中的行     這時 count 就派上用場了     ...
閱讀完整內容