e538 - 11389 - The Bus Driver Problem
題目描述
題目要求計算將 n 個巴士司機分配到 n 條早晨路線和 n 條傍晚路線，使得總加班費最小。加班費的計算方式是，如果一個司機一天的總路線長度超過 d，則需要支付 (總路線長度 - d) * r 的加班費。
解題思路
為了最小化加班費，我們應該將最短的早晨路線分配給最長的傍晚路線，將第二短的早晨路線分配給第二長的傍晚路線，以此類推。這樣可以盡可能地減少超過 d 的總路線長度。因此，我們首先對早晨路線和傍晚路線的長度進行排序，然後將排序後的早晨路線和傍晚路線配對，計算每位司機的加班費，並將所有司機的加班費加總。
複雜度分析
- 時間複雜度: O(n log n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int n,d,r;
while(cin >> n >> d >> r){
if(d==0&&n==0&&r==0)break;
int a[n],b[n],ans=0;
for(int i=0;i<n;++i){
cin >> a[i];
}
for(int i=0;i<n;++i){
cin >> b[i];
}
sort(a,a+n);
sort(b,b+n);
for(int i=0,ni=n-1;i<n;++i,--ni){
int tmp=a[i]+b[ni]-d;
if(tmp>0)ans+=tmp*r;
}
cout << ans << "\n";
}
}