[LeetCode]406 Queue Reconstruction by Height（BIT，二分）
题目链接：https://leetcode.com/problems/queue-reconstruction-by-height/?tab=Description
题意：给一个队列，每个人的身高以及他们前面的比他高的人的数量。求重构这个队列。
很简单，以前意淫过一道类似的题，不过是逆序数。这道题明显条件多了一点，不过不影响。
按照身高从小到大排序，然后在此基础上按照逆序数从大到小排序。用树状数组维护[1,pos]的总的空白位置数量，每次插入的时候从头到尾插，二分找到最左边的满足条件的位置后，更新空白数量-1即可。
甚至感觉像在写模拟。
1 class Solution { 2 public: 3 int n, bit[1100]; 4 int lowbit(int x) { 5 return x & (-x); 6 } 7 void update(int i, int x) { 8 while(i <= n) { 9 bit[i] += x; 10 i += lowbit(i); 11 } 12 } 13 int sum(int i) { 14 int ret = 0; 15 while(i) { 16 ret += bit[i]; 17 i -= lowbit(i); 18 } 19 return ret; 20 } 21 int lb(int val) { 22 int lo = 1, hi = n; 23 while(lo <= hi) { 24 int mid = (lo + hi) >> 1; 25 int x = sum(mid); 26 if(x >= val) hi = mid - 1; 27 else lo = mid + 1; 28 } 29 return lo; 30 } 31 static bool cmp(const pair<int, int>& a, const pair<int, int>& b) { 32 if(a.first != b.first) return a.first < b.first; 33 return a.second > b.second; 34 } 35 vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) { 36 pair<int, int> ret[1100]; 37 memset(bit, 0, sizeof(bit)); 38 n = people.size(); 39 for(int i = 2; i <= n; i++) update(i, 1); 40 sort(people.begin(), people.end(), cmp); 41 for(int i = 1; i <= n; i++) { 42 int pos = lb(people[i-1].second+1); 43 update(pos, -1); 44 ret[pos-1].first = people[i-1].first; 45 ret[pos-1].second = people[i-1].second; 46 } 47 people.clear(); 48 for(int i = 1; i <= n; i++) people.push_back(ret[i]); 49 return people; 50 } 51 };