https://leetcode.com/contest/6/problems/queue-reconstruction-by-height/
分析:每个表示成(a,b)的形式,其实找第一个,就是b为0,a最小的那一个,然后一次更新小于等于a的节点的序号b,就是b--,然后重复上面的过程。
我刚开始是按a排序,然后再按b排序,使用set来做,发现我还要修改set元素的值,发现不能修改,(这里还是对数据结构掌握的不透彻),左后使用vector来做,不断的进行排序,来维护顺序。代码写的有点乱,感觉还是紧张。
还有刚开始我在codeblock上调的,粘到leetcode,忘记修改node的比较函数,然后就罚时了。:(
struct node {
int h, n, v;
bool operator<(const node & a) const {
if(n == a.n) {
return h < a.h;
}
return n < a.n;
}
};
class Solution {
public: vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people) {
int n = people.size();
vector<pair<int, int> > res;
if(n < ) return people;
set<node> se;
vector<node> v;
for (auto x : people) {
//se.insert({x.first, x.second, x.second});
v.push_back({x.first, x.second, x.second});
}
//cout << "asd" << endl;
sort(v.begin(), v.end());
for (int i = ; i < n; i++) {
for (int j = ; j < v.size(); j++) {
if(v[j].h <= v[].h) {
v[j].n--;
}
}
res.push_back({v[].h, v[].v });
v.erase(v.begin());
sort(v.begin(), v.end());
}
return res;
} };