主題

ZeroJudge - e593: 12382 - Grid of Lamps　解題心得

Not In My Back Yard | 2020-01-07 15:25:14 | 巴幣 4 | 人氣 410

題目連結：

題目大意：

給定一正整數 T （T ≦ 100），代表有 T 筆測試資料，每筆佔三列。測資的第一列給定兩正整數 M 、 N （1 ≦ M 、 N ≦ 1000），代表一 M 列 N 行的燈泡陣列；接著第二列給定 M 個非負整數，代表 M 列燈泡燈亮的情形（每個值代表一列要亮的燈泡數）；第三列給定 N 個非負整數，代表 N 行燈泡燈亮的情形。

一開始所有燈泡都是暗的。試問，要點亮至少多少燈泡才能滿足上述給定的燈亮情形（不一定要照順序）。

範例輸入：

3

2 2

2 0

0 2

1 4

2

1 0 1 1

2 4

3 1

0 2 1 2

範例輸出：

3

5

解題思維：

因為要盡可能地點亮越少的燈泡。因此，我們需要找到越多的交叉點，使得同時可以滿足行列的需求（即同時可以抵消行列的需求）。

因此，將所有行（或是列）的亮燈需求由大排到小。然後一顆一顆點亮去抵銷行列的需求（每點亮一顆，行（或是列）的需求需要重新排列一次，所以用優先佇列（Priority Queue）會比較快）。

如果行（或是列）的需求沒有了，但是列（或是行）還有剩的話，那就直接將剩下的全部加入答案之中即可（一定找得到地方點亮燈炮）。

本人的程式碼（於 CodePile 上）

此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。

#程式題目解題心得 #貪心演算法（Greedy Algorithm）#優先佇列（Priority Queue）#堆積（Heap）

2

留言

創作回應

還有 1 則留言

Not In My Back Yard

不好意思，已修正。

2020-01-07 19:15:31

心彩

這題不懂 "一顆一顆點亮去抵銷行列的需求" 譬如某一列有n個需求我要怎麼知道要加在哪幾行

2023-06-16 09:00:22

Not In My Back Yard

就直接從需求量最大的行開始點亮即可，不過因為同一行在同一列不能被點亮兩次所以不能直接把該行丟回到優先佇列中要先存在另一個暫存的地方才行（之後再加回去）。

2023-06-16 12:43:33

心彩

可以舉例？點亮是怎樣操作的嗎？

2023-06-16 12:53:55

心彩

意思是我這行有n個燈要點就選前n個需求最高的列來點就對了嗎?

2023-06-16 13:08:04

Not In My Back Yard

是的。而如果不足 n 個則剩下的隨便點亮即可（一定有地方可以點亮）。

2023-06-16 14:30:14

心彩

buffer = lightsRow.top(), lightsRow.pop();
while (buffer && !lightsColumn.empty()) {
buffer2 = lightsColumn.top(), lightsColumn.pop();
--buffer2, --buffer, ++counts;
if (buffer2)
temporary.push(buffer2);
}
counts += buffer;

這裡的buffer 不是必定會用完 "--buffer, ++counts;" 這兩個應該可以不用寫

2023-06-16 17:27:05

心彩

噢我知道了 buffer 還會當作條件我是把 counts += buffer; 寫在前面

2023-06-16 17:49:25