Codeforces 4B Before an Exam 在一場考試之前

難易度 : 1200

英文原文如下

Tomorrow Peter has a Biology exam. He does not like this subject much, but d days ago he learnt that he would have to take this exam. Peter’s strict parents made him prepare for the exam immediately, for this purpose he has to study not less than minTime_i and not more than maxTime_i hours per each i-th day. Moreover, they warned Peter that a day before the exam they would check how he has followed their instructions.

So, today is the day when Peter’s parents ask him to show the timetable of his preparatory studies. But the boy has counted only the sum of hours sumTime spent him on preparation, and now he wants to know if he can show his parents a timetable sсhedule with d numbers, where each number sсhedule_i stands for the time in hours spent by Peter each i-th day on biology studies, and satisfying the limitations imposed by his parents, and at the same time the sum total of all schedule_i should equal to sumTime.

中文翻譯

Peter 在明天有一個生物考試。他不太喜歡這個科目，但在 d 天以前他就知道有這個考試。Peter嚴厲的父母命令他馬上開始準備考試，為了這個目的，他必須學習不少於 minTime_i 以及不超過 maxTime_i 小時在第 i天。此外，他們警告 Peter 在考試前一天他們會檢查他是否有遵照他們的指示。

因此，今天是 Peter 的父母要求他展示準備學習時間表的日子。但是這位男孩只算了他花在準備上的總時間sumTime，現在他想知道是否可以向他的父母展示一個時間表 schedule，其中包含d個數字，每個schedule_i代表 Peter 每天在生物學習上花費的時間，滿足他父母的限制條件，同時總和為 sumTime。

輸入

The first input line contains two integer numbers d, sumTime (1 ≤ d ≤ 30, 0 ≤ sumTime ≤ 240) — the amount of days, during which Peter studied, and the total amount of hours, spent on preparation. Each of the following d lines contains two integer numbers minTime_i, maxTime_i (0 ≤ minTime_i ≤ maxTime_i ≤ 8), separated by a space — minimum and maximum amount of hours that Peter could spent in the i-th day.

第一行包含了兩個整數 d, sumTime (1 ≤ d ≤ 30, 0 ≤ sumTime ≤ 240) — 分別是 Peter 學習的天數以及準備的總時數。接下來的 d 行則都包含了兩個整數  minTime_i, maxTime_i (0 ≤ minTime_i ≤ maxTime_i ≤ 8)，用空白間隔 — 代表著 Peter 第 i 天可以學習最小以及最大的時數。

輸出

In the first line print YES, and in the second line print d numbers (separated by a space), each of the numbers — amount of hours, spent by Peter on preparation in the corresponding day, if he followed his parents’ instructions; or print NO in the unique line. If there are many solutions, print any of them.

如果第一行印出 YES，下一行就要印出 d 個數字(用空白分隔)，每一個數字代表著 — 小時的單位，Peter 每天花在準備上的時間，當然前提是如果他能遵守他爸媽的指示。要是無法，則印出 NO。而要是有多種解答 (每日時間)，則印出任一一個就好。

範例

解題思路

在這一題中，我們的解決方案會使用兩個迴圈來處理

最原本的想法其實是用3個迴圈，第一個讀取資料，第二個跑最小單位，若有剩餘則跑第三個迴圈這樣

後來將讀取資料，以及跑最小單位合併

簡單講解一下大致的思路

總而言之，最大的目標就是要讓每一天取一個時間 (介於 minTime_i 以及 maxTime_i 之間)，並讓其總和等於 sumTime 

那最簡單的方式就是讓每一天先以 minTime 來計算，若有剩餘，再去 max – min 中取值來計算

當然若第一個最小的迴圈就超過 sumTime，則我們也救不了 Peter 了哈哈…

C#解決方案

方案1

string[] first = Console.ReadLine().Split(' '); //split by space
int d = int.Parse(first[0]);    //days
int sumTime = int.Parse(first[1]); 

int[]minArr = new int[d];   //min value also use as the result
int[]leftArr = new int[d];

for(int i=0;i<d;i++)
{
    var arr = Console.ReadLine().Split(' ');
    var min = int.Parse(arr[0]);  
    var max = int.Parse(arr[1]);  
    
    sumTime-=min;
    minArr[i] = min;
    leftArr[i] = max-min;
}

if(sumTime==0){
    Console.WriteLine("YES");
    Console.WriteLine(String.Join(" ", minArr));
}
else if(sumTime<0){
        Console.WriteLine("NO"); 
}
//still need more time
else{
    for(int i=0;i<d;i++)
    {
        if(sumTime>leftArr[i]){
            sumTime -= leftArr[i];
            minArr[i]+=leftArr[i];
        }
        else{
            minArr[i]+=sumTime;
            sumTime = 0;
            Console.WriteLine("YES");
            Console.WriteLine(String.Join(" ", minArr));
            break;
        }
    }
}

//still need more time!!
if(sumTime>0){
    Console.WriteLine("NO"); 
}

其中的 minArr 被視為第一次最小的值以及最後的結果

要是跑完min value 還有剩餘的時數，就要對剩餘可行的時間 (max-min) 迴圈

並會更新 minArr的內容

Java解決方案

方案1

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] first  = scanner.nextLine().split(" ");
        
        int d = Integer.parseInt(first[0]);    //days
        int sumTime = Integer.parseInt(first[1]); 
        
        int[]minArr = new int[d];   //min value also use as the result
        int[]leftArr = new int[d];
        
        for(int i=0;i<d;i++)
        {
            String[] arr = scanner.nextLine().split(" ");
            int min = Integer.parseInt(arr[0]);  
            int max = Integer.parseInt(arr[1]);  
            
            sumTime-=min;
            minArr[i] = min;
            leftArr[i] = max-min;
        }
        
        if(sumTime==0){
            System.out.println("YES");
            System.out.println(String.join(" ", Arrays.stream(minArr).mapToObj(String::valueOf).toArray(String[]::new)));
        }
        else if(sumTime<0){
                System.out.println("NO"); 
        }
        //still need more time
        else{
            for(int i=0;i<d;i++)
            {
                if(sumTime>leftArr[i]){
                    sumTime -= leftArr[i];
                    minArr[i]+=leftArr[i];
                }
                else{
                    minArr[i]+=sumTime;
                    sumTime = 0;
                    System.out.println("YES");
                    System.out.println(String.join(" ", Arrays.stream(minArr).mapToObj(String::valueOf).toArray(String[]::new)));
                    break;
                }
            }
        }
        
        //still need more time!!
        if(sumTime>0){
            System.out.println("NO"); 
        }
    }
}

唯一與C#不同的地方是，Java 的 String.join 只能對string陣列做，所以要特別進行個轉型

結論

這一題是某一次系列中的第二題，第一題的解析可以在這裡找到 ➡ Codeforces 4A 西瓜

最近都在寫第一題，第二題的難度唰一下就起來了哈哈

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

🧡收藏文章或幫我點個廣告，那都是對我的支持

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

題目連結 : Problem – 4B – Codeforces

一些其他的Codeforces文章