g774 - 校隊 (School Team)
題目描述
題目要求從 $N + M$ 個班級中選出 $N$ 名男生和 $M$ 名女生，使得總跑步時間最短。每班必須選出一人，且必須是該班級同性別中跑百米最快的人。
解題思路
這個問題可以使用貪心演算法解決。首先，計算所有班級的男生和女生總跑步時間。然後，按照每個班級的「女生跑速 - 男生跑速」進行排序。對於排序後的前 $M$ 個班級，選擇女生；對於剩下的 $N$ 個班級，選擇男生。這樣可以確保總跑步時間最小化。排序的目的是為了優先選擇女生比男生跑得快的班級，這樣可以減少總時間。
複雜度分析
- 時間複雜度: O((N+M)log(N+M))
- 空間複雜度: O(N+M)
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
long long n,m,ans;
pair <long long,long long> a[4005];
bool cmp(pair <long long,long long> x,pair <long long,long long> y){
long long c=x.second-x.first,d=y.second-y.first;
if(c<d)return 1;
return 0;
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
for(int i=0;i<n+m;++i){
cin >> a[i].first >> a[i].second;
ans+=a[i].first;
}
sort(a,a+n+m,cmp);
for(int i=0;i<m;++i){
ans-=(a[i].first-a[i].second);
}
cout << ans;
}