e593 - 12382 - Grid of Lamps
題目描述
題目描述一個 M x N 的網格，給定每行和每列至少需要亮燈的數量。初始時所有燈都是熄滅的。目標是計算點亮最少數量的燈，以滿足每行和每列的最低亮燈要求。
解題思路
這個問題可以使用貪心演算法來解決。首先，將每行的亮燈需求排序，然後將每列的亮燈需求放入優先佇列中。接著，從亮燈需求最高的行開始，盡可能使用優先佇列中的燈來滿足該行的需求。如果優先佇列中的燈不足以滿足該行的需求，則需要額外點亮燈。在處理完所有行後，優先佇列中剩餘的燈也需要被點亮。
具體步驟如下：
- 讀取 M 和 N。
- 讀取每行的亮燈需求，並將其排序。
- 讀取每列的亮燈需求，並將其放入優先佇列中。
- 從最後一行開始，迭代處理每一行。
- 對於每一行，盡可能使用優先佇列中的燈來滿足該行的需求。
- 如果優先佇列中的燈不足以滿足該行的需求，則額外點亮燈。
- 將已使用的燈放入一個臨時佇列中。
- 將臨時佇列中的燈放回優先佇列中。
- 處理完所有行後，將優先佇列中剩餘的燈全部點亮。
- 輸出總共點亮的燈的數量。
複雜度分析
- 時間複雜度: O(N log N + M log M + M log N)
- 排序每行的需求：O(M log M)
- 建立優先佇列：O(N log N)
- 迭代 M 行，每次從優先佇列中取出元素：O(M log N)
- 空間複雜度: O(N + M)
- 儲存每行的需求：O(M)
- 優先佇列：O(N)
- 臨時佇列：O(M)
程式碼
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int t,n,m,k,a[1005];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
int ans=0;
cin >> n >> m;
priority_queue <int> q;
for(int i=0;i<n;++i){
cin >> a[i];
}
sort(a,a+n);
for(int i=0;i<m;++i){
cin >> k;
if(k)q.push(k);
}
for(int i=n-1;i>=0;--i){
queue <int> tmp;
while(a[i]&&q.empty()==0){
tmp.push(q.top()-1);
q.pop();
--a[i];
++ans;
}
ans+=a[i];
while(tmp.empty()==0){
if(tmp.front())
q.push(tmp.front());
tmp.pop();
}
}
while(q.empty()==0){
ans+=q.top();
q.pop();
}
cout << ans << "\n";
}
}