Codeforces 158B Taxi 計程車

Klook.com
文章觀看次數: 138

難易度 : 1100

英文原文如下

After the lessons n groups of schoolchildren went outside and decided to visit Polycarpus to celebrate his birthday. We know that the i-th group consists of si friends (1 ≤ si ≤ 4), and they want to go to Polycarpus together. They decided to get there by taxi. Each car can carry at most four passengers. What minimum number of cars will the children need if all members of each group should ride in the same taxi (but one taxi can take more than one group)?

中文翻譯

在課程結束後，n 組學生決定去拜訪 Polycarpus 來慶祝他的生日，我們知道第 i 組學生包含了 si 位朋友 (1 ≤ si ≤ 4)，而且他們會一起前往 Polycarpus 那。他們決定要搭計程車來前往，每一台車最多可以載 4 位乘客。現在要計算最少的計程車數來讓所有的學生組別可以每組都在同一台車上(但一台計程車可以載超過一組學生)

輸入

The first line contains integer n (1 ≤ n ≤ 105) — the number of groups of schoolchildren. The second line contains a sequence of integers s1, s2, …, sn (1 ≤ si ≤ 4). The integers are separated by a space, si is the number of children in the i-th group.

第一行包含了整數 n (1 ≤ n ≤ 105) — 學生群組的數量。第二行包含了一個整數序列 s1, s2, …, sn (1 ≤ si ≤ 4)。這些整數由空白間隔，si 就是第 i 組學生的人數。

輸出

Print the single number — the minimum number of taxis necessary to drive all children to Polycarpus.

印出一個數字 — 將所有的學生組別載到 Polycarpus 那需要最少的計程車數

範例

輸入5
1 2 4 3 3
輸出4
輸入8
2 3 4 4 2 1 3 1
輸出5

解題思路

在第一次嘗試中，我對學生組別進行了一次 for loop

再嘗試中，會盡量將學生湊成一車 ➡ 3+1、4 可以直接搭車、2+2…

另外若是沒辦法湊成一車，也會想辦法將學生往後湊，可以看到每一段都有 arr[i] = 0; 也就是將當前的人數清空

整體邏輯上來說沒問題，但卻超過程式的時限，畢竟在 for loop 裡面又去indexOf，最少也是個 O(n2)

C#解決方案

第一次嘗試 – 超時 Time limit exceeded 

int n = int.Parse(Console.ReadLine());  //number of groups 

int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int carCnt = 0;

for(int i=0; i<arr.Length;i++){
    int num = arr[i];   // number of children in the group
    
    if(num==4){
        carCnt+=1;
        arr[i] = 0;
    }
    else if(num==3){
        var idx = Array.IndexOf(arr,1);
        if(idx>-1){
            carCnt+=1;
            arr[i] = 0;
            arr[idx] = 0;
        }
    }
    else if(num==2){
        var idx = Array.LastIndexOf(arr,2);
        if(idx>-1 && idx != i){
            carCnt+=1;
            arr[i] = 0;
            arr[idx] = 0;
            continue;
        }
        idx = Array.IndexOf(arr,1);
        if(idx>-1){
            arr[i] = 0;
            arr[idx] = 3;
        }
    }
    else if(num==1) {
        var idx = Array.IndexOf(arr,3);
        if(idx>-1){
            carCnt+=1;
            arr[i] = 0;
            arr[idx] = 0;
            continue;
        }
        
        idx = Array.LastIndexOf(arr,2);
        if(idx>-1){
            arr[i] = 0;
            arr[idx] = 3;
            continue;
        }
        
        idx = Array.LastIndexOf(arr,1);
        if(idx>-1 && idx != i){
            arr[i] = 0;
            arr[idx] = 2;
            continue;
        }
    }
    
}

int nonZeroCount = arr.Count(x => x > 0);
Console.WriteLine(carCnt+nonZeroCount);

思考後修正了整個寫法

畢竟對於要怎麼計算其實是知道的 (湊成一車)

那我們幹嘛執著於 index呢，這樣還要浪費時間來多進行判斷

故很快就修正了寫法

方案1

int n = int.Parse(Console.ReadLine());  //number of groups 
 
int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int carCnt = 0;
int cnt1 = 0;
int cnt2 = 0;
int cnt3 = 0;


foreach(var a in arr){
    if(a==1){
        cnt1+=1;
    }
    else if(a==2){
        cnt2+=1;
    }
    else if(a==3){
        cnt3+=1;
    }
    else{   //4
        carCnt+=1;
    }
}

while(cnt3>0 && cnt1>0){
    cnt3-=1;
    cnt1-=1;
    carCnt+=1;
}

while(cnt1>1){
    cnt1-=2;
    cnt2+=1;
}

while(cnt2>1){
    cnt2-=2;
    carCnt+=1;
}

// If there is exactly one cnt1 and one cnt2, they can be combined into one taxi
if(cnt1==1 && cnt2==1){
    Console.WriteLine(carCnt+1+cnt3);
}
else{
    Console.WriteLine(carCnt+cnt1+cnt2+cnt3);
}

用 while 來判斷是否還有足夠的組別可以湊成一台車 (四人的組別讀取時，直接算一台車了)

  • while(cnt3>0 && cnt1>0) : 判斷 3+1
  • while(cnt2>1) : 判斷 2+2，但在那之前會先將兩個一人組視為一個二人組

最後再透過剩餘的判斷，來將其他人趕上車 (最後的 if-else，這裡的就沒湊齊4個人)

結論

第一次嘗試想得太複雜了，還保留了index的判斷，完全忘記應該直接從根本下手啊

這一題出自於這個系列 – Dashboard – VK Cup 2012 Qualification Round 1 – Codeforces

這裡來看第一題的解析 ➡ Codeforces 158A 下一輪 – 翻譯與解答

🧡如果文章有幫上你的忙，那是我的榮幸

🧡可以的話，可以動動您的小手幫我分享一下就太好了

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Problem – 158B – Codeforces

一些其他的Codeforces文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *