d774 - NOIP2009 2.分数线划定
題目描述
題目要求根據給定的報名人數 n 和計劃錄取人數 m，計算出分數線，並輸出所有達到分數線或超過分數線的選手的報名號和筆試成績。分數線的計算方式是取排名第 m * 1.5 向下取整的選手的分數。
解題思路
首先，將所有選手的報名號和筆試成績儲存在一個 pair 陣列中。然後，按照筆試成績降序排序。接著，計算分數線，即排名第 m * 1.5 向下取整的選手的分數。最後，遍歷排序後的陣列，輸出所有筆試成績大於等於分數線的選手的報名號和筆試成績，按照筆試成績降序輸出，如果成績相同，則按照報名號升序輸出。
複雜度分析
- 時間複雜度: O(n log n)，主要來自排序操作。
- 空間複雜度: O(n)，主要來自儲存選手資料的陣列。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int n,m,mi,it;
pair <int,int> a[5005],b[5005];
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> n >> m;
m=m*1.5;
for(int i=1;i<=n;++i){
cin >> a[i].second >> a[i].first;
a[i].second*=-1;
}
sort(a+1,a+n+1);
mi=a[n-m+1].first;
for(int i=n;i>=n-m;){
while(a[i].first>=mi){
b[it]=a[i];
++it;
--i;
}
if(a[i].first<mi)break;
}
cout << mi << " " << it << "\n";
for(int i=0;i<it;++i){
cout << -b[i].second << " " << b[i].first << "\n";
}
}