Codeforces 427A Police Recruits 警員的招募

難易度 : 800

英文原文如下

The police department of your city has just started its journey. Initially, they don’t have any manpower. So, they started hiring new recruits in groups.

Meanwhile, crimes keeps occurring within the city. One member of the police force can investigate only one crime during his/her lifetime.

If there is no police officer free (isn’t busy with crime) during the occurrence of a crime, it will go untreated.

Given the chronological order of crime occurrences and recruit hirings, find the number of crimes which will go untreated.

中文翻譯

在你城市的警察局才剛開始營業。最初，他們沒有任何的人力，所以他們開始招募警員。

與此同時，城市中的犯罪不斷發生。一個警員在他/她的一生中只能調查一起犯罪。

要是當一個犯罪發生時，沒有任一個警員閒置(無調查犯罪)，則該犯罪就不會被處理。

根據犯罪事件和招募的時間順序，找出會不被處理的犯罪數量。

輸入

The first line of input will contain an integer n (1 ≤ n ≤ 10⁵), the number of events. The next line will contain n space-separated integers.

If the integer is -1 then it means a crime has occurred. Otherwise, the integer will be positive, the number of officers recruited together at that time. No more than 10 officers will be recruited at a time.

輸入的第一行包含了一個整數  n (1 ≤ n ≤ 10⁵)，也就是有多少事件發生(招募警員或是發生犯罪)。下一行包含了 n 個用空格分隔的整數。

要是整數是 -1 代表有一件犯罪發生，否則整數會是正整數(大於0)，代表了有多少個員警同時被招募。同時不會超過10個員警被招募。

輸出

Print a single integer, the number of crimes which will go untreated.

印出一個整數，也就是有多少件沒有被處理的犯罪。

範例

解題思路

可以簡單的用幾個變數來解決這個問題

一個存目前閒置的警力，一個則存多少件未處理的犯罪

C#解決方案

方案1

int n = int.Parse(Console.ReadLine());
int[]arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); //split by space

int curr=0;
int cnt=0;

foreach(var item in arr){
    curr+=item;
    
    if(curr<0){
        cnt += Math.Abs(curr);
        curr = 0;
    }
}

Console.WriteLine(cnt);

要是當前警力在事件後小於0，則代表犯罪未經處理，則加上其差值，並將警力改回 0

(翻譯的時候，發現題目中有說一次只會有一個犯罪發生，故又精簡了該寫法)

方案1.1 修正版 (犯罪一次僅一件)

int n = int.Parse(Console.ReadLine());
int[]arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); //split by space

int curr=0;
int cnt=0;

foreach(var item in arr){
    curr+=item;
    
    if(curr<0){
        cnt += 1;
        curr = 0;
    }
}

Console.WriteLine(cnt);

結論

偶爾在回顧題目的時候，才會發現原來有地方沒注意到…

真是慚愧，大家看到文章有誤還請多擔待並提醒筆者下~ 感激不盡

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

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

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

題目連結 : Problem – 427A – Codeforces

一些其他的Codeforces文章