立志用最少的代碼做最高效的表達

---

PAT甲級最優題解——>傳送門

---

Forbes magazine publishes every year its list of billionaires based on the annual ranking of the world’s wealthiest people. Now you are supposed to simulate this job, but concentrate only on the people in a certain range of ages. That is, given the net worths of N people, you must find the M richest people in a given range of their ages.

Input Specification:
Each input file contains one test case. For each case, the first line contains 2 positive integers: N (≤10^?5??) - the total number of people, and K (≤10?3??) - the number of queries. Then N lines follow, each contains the name (string of no more than 8 characters without space), age (integer in (0, 200]), and the net worth (integer in [?10?6??,10?6??]) of a person. Finally there are K lines of queries, each contains three positive integers: M (≤100) - the maximum number of outputs, and [Amin, Amax] which are the range of ages. All the numbers in a line are separated by a space.

Output Specification:
For each query, first print in a line Case #X: where X is the query number starting from 1. Then output the M richest people with their ages in the range [Amin, Amax]. Each person’s information occupies a line, in the format

Name Age Net_Worth
The outputs must be in non-increasing order of the net worths. In case there are equal worths, it must be in non-decreasing order of the ages. If both worths and ages are the same, then the output must be in non-decreasing alphabetical order of the names. It is guaranteed that there is no two persons share all the same of the three pieces of information. In case no one is found, output None.

Sample Input:
12 4
Zoe_Bill 35 2333
Bob_Volk 24 5888
Anny_Cin 95 999999
Williams 30 -22
Cindy 76 76000
Alice 18 88888
Joe_Mike 32 3222
Michael 5 300000
Rosemary 40 5888
Dobby 24 5888
Billy 24 5888
Nobody 5 0
4 15 45
4 30 35
4 5 95
1 45 50

Sample Output:
Case #1:
Alice 18 88888
Billy 24 5888
Bob_Volk 24 5888
Dobby 24 5888
Case #2:
Joe_Mike 32 3222
Zoe_Bill 35 2333
Williams 30 -22
Case #3:
Anny_Cin 95 999999
Michael 5 300000
Alice 18 88888
Cindy 76 76000
Case #4:
None

---

題意：N個土豪，分K次查詢。
每個人有三個參數：名字、年齡、財富。 輸入最多查詢的人數，輸入年齡區間查詢后輸出。

分析：

用C++寫了兩版代碼，但全都超時，逐一調試后發現是string的原因。

我們知道：如果想加快cin、cout輸入輸出速度，需要取消流同步，即：ios::sync_with_stdio(false);。 一般來說，取消流同步后的C++，速度相較于scanf、printf更快。

但如果程序中有string型字符串， 那么即便取消流同步后，C++的速度還是會慢于C 。因此， 本題的名字采用char[]數組存儲，輸入輸出采用C的寫法。

剪枝：
由于最多查詢一百位。 因此，如果有相同年齡的人數超過了100，那么以后的人都可以不用放入數組了。

---

測試點一：總人數非常多，考查排序效率。

測試點二：在同一年齡的人非常多。 考查剪枝。

---

#include<bits/stdc++.h> using namespace std;struct people{char name[20];int age, worth; };bool cmp(people p1, people p2) {if(p1.worth != p2.worth) return p1.worth > p2.worth;else if(p1.age != p2.age) return p1.age < p2.age;else return strcmp(p1.name,p2.name) < 0; } int book[205] = {0}; int main() {int n, k; scanf("%d %d", &n, &k);people peo; vector<people>v, v1;for(int i = 0; i < n; i++) {scanf("%s %d %d", peo.name, &peo.age, &peo.worth);v.push_back(peo);}sort(v.begin(), v.end(), cmp);for(int i = 0; i < n; i++) {if(book[v[i].age] < 100) {v1.push_back(v[i]); book[v[i].age]++;}}for(int i = 0; i < k; i++) {printf("Case #%d:\n", i + 1);int num, max_age, min_age, flag = false, l = 0; scanf("%d %d %d", &num, &min_age, &max_age);for(auto i : v) {if(i.age <= max_age && i.age >= min_age) {flag = true; if(l++ == num) break;printf("%s %d %d\n", i.name, i.age, i.worth);}}if(!flag) { printf("None\n"); continue; }}return 0; }

---

耗時：

---

求贊哦~ (?ω?)

總結

以上是生活随笔為你收集整理的【附超时原因】1055 The World‘s Richest (25 分)_42行代码AC的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。