Codeforces 282B Painting Eggs 蛋的彩繪

難易度 : 1500

英文原文如下

The Bitlandians are quite weird people. They have very peculiar customs.

As is customary, Uncle J. wants to have n eggs painted for Bitruz (an ancient Bitland festival). He has asked G. and A. to do the work.

The kids are excited because just as is customary, they’re going to be paid for the job!

Overall uncle J. has got n eggs. G. named his price for painting each egg. Similarly, A. named his price for painting each egg. It turns out that for each egg the sum of the money both A. and G. want for the painting equals 1000.

Uncle J. wants to distribute the eggs between the children so as to give each egg to exactly one child. Also, Uncle J. wants the total money paid to A. to be different from the total money paid to G. by no more than 500.

Help Uncle J. Find the required distribution of eggs or otherwise say that distributing the eggs in the required manner is impossible.

中文翻譯

比特蘭人是一群相當奇特的人，擁有非常獨特的習俗。

按照慣例，Uncle J.希望為比特魯茲（一個古老的比特蘭節日）繪製n顆蛋。他已經請求G.和A.完成這項工作。

孩子們很興奮，因為正如慣例，他們將得到報酬！

整理來說，Uncle J.有n顆蛋。G.給每顆蛋都要求了彩繪的價格，同樣地，A.也給每顆蛋都報價了。結果發現，對於每顆蛋，A.和G.要求的金額總和為1000。

Uncle J.希望在孩子們之間分發這些蛋，使每顆蛋都只分發給一個孩子。此外，Uncle J.希望支付給A.的總金額與支付給G.的總金額之間的差額不超過500。

若可以達成則幫助Uncle J.找到所需的蛋分配方式，否則輸出無法達成分配。

輸入

The first line contains integer n (1 ≤ n ≤ 10⁶) — the number of eggs.

Next n lines contain two integers a_i and g_i each (0 ≤ a_i, g_i ≤ 1000; a_i + g_i = 1000): a_i is the price said by A. for the i-th egg and g_i is the price said by G. for the i-th egg.

第一行包含了整數 n (1 ≤ n ≤ 10⁶) — 蛋的數量。

接下來的 n 行包含了兩個整數 a_i 跟 g_i  (0 ≤ a_i, g_i ≤ 1000; a_i + g_i = 1000)，a_i 就是A對第 i 顆蛋的報價， g_i 則是G對第 i 顆蛋的報價。

輸出

If it is impossible to assign the painting, print “-1” (without quotes).

Otherwise print a string, consisting of n letters “G” and “A”. The i-th letter of this string should represent the child who will get the i-th egg in the required distribution. Letter “A” represents A. and letter “G” represents G. If we denote the money Uncle J. must pay A. for the painting as S_a, and the money Uncle J. must pay G. for the painting as S_g, then this inequality must hold: |S_a  -  S_g|  ≤  500.

If there are several solutions, you are allowed to print any of them.

如果無法分配蛋的彩繪的話，印出”-1″(不需要引號)。

否則，請輸出一個由n個字母”G”和”A”組成的字串。這個字串的第i個字母應表示將獲得第i個蛋的孩子。字母”A”代表A，字母”G”代表G。如果我們將 Uncle J. 必須支付給A的繪畫費用表示為S_a，將支付給G的繪畫費用表示為S_g，則必須滿足以下不等式：S_a  -  S_g|  ≤  500。

如果有多個解答，可以輸出其中的任何一個。

範例

解題思路

這一題的主要解題節奏就是希望讓兩個小孩的差額越小越好

所以在我第一次的嘗試中，採用了以下的方式

• 初始化一個sum作為總和，並將A視為正，G視為負的報價 (用以判斷兩者差額)
• 迴圈並記錄A 以及 G的報價
• 計算兩個可能的差額 tmp1 以及 tmp2 ，分別是本次選擇A或是選擇G後的總差額
• 用Math.Abs 判斷兩者會有更小的差值，並選擇他的報價
• 直到所有蛋被選擇完，最後判斷總差值是否大於 500 (>500 or <-500)，若無則輸出報價結果，若超過則印出 -1 (無法完成)

C#解決方案

第一次嘗試 – 超時 Time limit exceeded 

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

int sum = 0;
string res = "";

for(int i=0; i<n;i++){
    string[] arr = Console.ReadLine().Split(' '); //split by space
    int a = int.Parse(arr[0]);
    int g = int.Parse(arr[1]);
    
    int tmp1 = sum+a;
    int tmp2 = sum-g;
    
    if(Math.Abs(tmp1)<Math.Abs(tmp2)){
        res+="A";
        sum = tmp1;
    }
    else{
        res+="G";
        sum = tmp2;
    }
}

if(Math.Abs(sum)>500){
    Console.WriteLine("-1");
}
else
{
    Console.WriteLine(res);
}

看起來，題目B 跟超時非常有緣呢，那讓我們來看下哪裡還能改善的

• 首先，題目有說道 A+G的報價會為1000，故我們可以不用 int.Parse(arr[1])，直接用1000-A的報價就好，這樣可以每次都省下一個轉型的消耗
• 第二，字串其實不適合進行大量的修改操作，因為在底層其實是建立一個新的物件並儲存，故對於效能不管說是儲存空間還是速度來說都是很大的損耗，故改用 char[] 或是 StringBuilder都會比較合適

方案1

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

int sum = 0;
string res = "";
char[] resArr = new char[n];

for(int i=0; i<n;i++){
    string[] arr = Console.ReadLine().Split(' '); //split by space
    int a = int.Parse(arr[0]);
    //int g = int.Parse(arr[1]);
    int g = 1000 - a;
    
    int tmp1 = sum+a;
    int tmp2 = sum-g;
    
    if(Math.Abs(tmp1)<Math.Abs(tmp2)){
        //res+="A";
        resArr[i] = 'A';
        sum = tmp1;
    }
    else{
        //res+="G";
        resArr[i] = 'G';
        sum = tmp2;
    }
}

if(sum>500 || sum<-500){
    Console.WriteLine("-1");
}
else
{
    //Console.WriteLine(res);
    Console.WriteLine(new string(resArr));
}

當然是順利地執行通過囉~

結論

這一題延續了上一題的背景故事ㄟ哈哈~ 都是Bitland的

通常系列的第二題開始有點難度了，第一次嘗試蠻容易沒想清楚就失敗…

另外，StringBuilder的範例可以看這裡 LeetCode #844 Backspace字串比較，之後也可以專門寫一篇來特別講解下

今天這一題出自於這個系列 – Dashboard – Codeforces Round 173 (Div. 2) – Codeforces

這邊看第一題的解析 ➡ Codeforces 282A Bit++ – 翻譯與解答

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

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

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

題目連結 : Problem – 282B – Codeforces

一些其他的Codeforces文章