774. Minimize Max Distance to Gas Station | NOEY

774. Minimize Max Distance to Gas Station | NOEY

题意为：给定一些坐标点，表示坐标轴上已有的gas sta­tion，同时给定K，表示将要再插入K个gas sta­tion，插完以后使gas sta­tion之间的最大距离最小。

首先要从离散的点抽象出In­ter­val的概念，其实已有的gas sta­tion就是一个个In­ter­val。更为关键的是，这些in­ter­val可以视为永远不变，唯一变化的就是他们里边可能插入多少个K。基于这些in­ter­val，我们每次选择插入K的时候，只要选择插入当前所有in­ter­val中dist最大的那个，一直插入直到它比第二大小为止。插完所有的K，我们就得到了最后的解。

有了以上的理解，一个pri­or­ity_queue就可以轻易的解决问题，用addK()去up­date当前in­ter­val里的value，然后把up­date完的top重新插回pri­or­ity_queue。解法复杂度为O(klogn)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

struct Interval { int length, k, dist; Interval(int i) : length(i), k(1), dist(i) {} bool operator< (const Interval& other) const { return dist < other.dist; } void addK() { k++; dist = length/k; } }; priority_queue<Interval> buildQueue(const vector<int>& v) { vector<int> ret(v.size()); adjacent_difference(v.begin(), v.end(), ret.begin()); ret.erase(ret.begin()); return priority_queue<Interval>(ret.begin(), ret.end()); } int minMaxDist(const vector<int>& v, int k) { auto pq = buildQueue(v); int maxDist = (v.back() - v.front())/(k+1); // just for optimization while(k) { Interval top = pq.top(); pq.pop(); while(pq.top() < top || top.dist > maxDist) { top.addK(); k--; } pq.push(top); } return pq.top().dist; }

这题的难点在于正确理解题意并抽象化后找出算法，关键点在于：

• 由于最早给定的gas station，随着K的插入，变化的并不是interval，而是每个interval内部的dist。
• 只关注最后的最大距离，并不关心每个gas station插在了哪里

Read full article from 774. Minimize Max Distance to Gas Station | NOEY