e197 - 倒回收
題目描述
題目描述了板橋高中打掃時回收的情境。有 N 個學生和 M 種回收，每種回收有數量和距離。學生可以一次拿兩個回收籃，目標是最小化學生們走的总距離。
解題思路
本題的核心思想是貪心策略。首先，將回收按照距離排序。然後，從最遠的回收開始，盡可能配對回收，每次配對選擇距離相近的回收，以最小化 max(d_a, d_b) * 2 的值。由於每次只能拿兩個回收籃，如果某種回收的數量為奇數，則先將其中一個回收籃處理掉，再進行配對。
具體步驟如下：
- 讀取 N, M, d[i] 和 c[i]。
- 將回收按照距離 d[i] 排序。
- 從最遠的回收開始，如果回收數量大於 0，則嘗試配對。
- 如果回收數量為奇數，則將其中一個回收籃先處理掉。
- 計算配對回收的總距離，並累加到答案中。
- 重複步驟 3-5，直到所有回收都被處理完。
複雜度分析
- 時間複雜度: O(M log M)，主要來自排序操作。其餘操作的時間複雜度為 O(M)。
- 空間複雜度: O(M)，主要用於儲存回收的距離和數量。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int t,m,n;
pair <int,int> a[100005];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> m;
long long ans=0;
for(int i=1;i<=m;++i){
cin >> a[i].first;
}
for(int i=1;i<=m;++i){
cin >> a[i].second;
}
a[0].second=a[0].first=0;
sort(a+1,a+m+1);
for(int i=m;i>0;--i){
if(a[i].second){
if(a[i].second%2){
a[i].second++;
a[i-1].second--;
}
ans+=(a[i].second/2)*a[i].first*2;
a[i].second=0;
}
}
cout << ans << '\n';
}
}