题目大意：输入整数t，表示有t个测试样例。每个测试样例输入m和q，分别代表共有m个人和q个查询。接着有m行，每行代表一个人的信息，分别是id、年薪、身高。定义A的直接老板指的是m个人中，年薪比A大的且身高不低于A的身高人中年薪最低的人。定义A的下属是包括A的下属和A的下属的下属。接着q个查询每次输入一个id，查询该人的直接老板和下属的数量。
解题思路：排序递推。结构体Person包括id,salary,high属性。对年薪进行从小到大的排序，在目标id右侧找直接老板，在目标左边找下属数量。注意：从目标id往左，只要遇到身高高于目标id的身高就不能继续往左，因为此时更左侧的不是目标id的下属。
代码如下：
1 #include <iostream> 2 #include <algorithm> 3 #include <vector> 4 #include <map> 5 using namespace std; 6 7 struct Person { 8 int id; 9 int salary; 10 int high; 11 Person(int id_ = 0, int salary_ = 0, int high_ = 0) { 12 id = id_; 13 salary = salary_; 14 high = high_; 15 } 16 bool operator<(const Person &other) const { 17 if (salary < other.salary) { 18 return true; 19 } else { 20 return false; 21 } 22 } 23 }; 24 25 26 int main() { 27 int t; 28 cin >> t; 29 while (t--) { 30 int m, q; 31 cin >> m >> q; 32 vector<Person> persons; 33 map<int, pair<int, int> > mp; 34 int id, salary, high; 35 for (int i = 0; i < m; i++) { 36 cin >> id >> salary >> high; 37 persons.push_back(Person(id, salary, high)); 38 mp[id] = pair<int, int>(salary, high); 39 } 40 41 sort(persons.begin(), persons.end()); 42 43 for (int i = 0; i < q; i++) { 44 cin >> id; 45 pair<int, int> p = mp[id]; 46 salary = p.first; 47 high = p.second; 48 49 // 二分查找 在当前根据salary排序完的队列中用二分查找，找到目标salary 50 // 然后递推查找直系boss和下属的数量 51 52 int begin = 0; 53 int end = m; 54 while (begin + 1 != end) { 55 int mid = (begin + end) / 2; 56 if (salary < persons[mid].salary) { 57 end = mid; 58 } else { 59 begin = mid; 60 } 61 } 62 63 int subordinate = 0; 64 // begin 即 salary 对应的 person 65 for (int i = begin-1; i >= 0; i--) { 66 if (persons[i].high > high) break; 67 subordinate++; 68 } 69 70 int immediateBoss = 0; 71 for (int i = begin + 1; i < m; i++) { 72 if (persons[i].salary > salary && persons[i].high >= high) { 73 immediateBoss = persons[i].id; 74 break; 75 } 76 } 77 78 cout << immediateBoss << " " << subordinate << endl; 79 80 } 81 82 } 83 84 return 0; 85 }
原文：http://www.cnblogs.com/mchcylh/p/4873274.html