Go from left (0 position) to right. When you encounter a stone for the kth time, throw it to right if k is odd, or skip it if k is even.
Return the position of the rightmost stone when you will not encounter a stone any more.
Example Example 1:
Input: p = [1, 2], d = [5, 4] Output: 11 Explanation: First, the stone on the position 1 was thrown to 6. Then skip the stone on the position 2. Next the stone on the position 6 was thrown to 11. Last skip the stone on the position 11. Example 2:
Input: p = [1, 6], d = [5, 6] Output: 12 Explanation: First, the stone on the position 1 was thrown to 6. Then skip the stone on the position 6 (the larger one). Next the stone on the position 6 was thrown to 12. Last skip the stone on the position 12. Notice n <= 10^4 p[i] <= 10^5 d[i] <= 10^3 If two or more stones stay at the same position, you will meet the largest one (the one with the smallest d[i]) first. Means throwing or skipping larger stones first.
解法1：用最小堆 代码如下。应该还可以简化一点，那个Stone里面的index好像没用。
struct Stone{ int pos; int dist; int index; Stone(int p = 0, int d = 0, int id = 0) : pos(p), dist(d), index(id) {}; }; //min-heap struct cmp { bool operator() (const Stone & a, const Stone & b) { if (a.pos == b.pos) { return a.dist > b.dist; } else { return a.pos > b.pos; } } }; class Solution { public: /** * @param p: the position of the i-th stone * @param d: how far the stones can be stone * @return: the distance from the start point to the farthest stone. */ int getDistance(vector<int> &p, vector<int> &d) { int n = p.size(); if (n == 0) return 0; int result = p[0]; priority_queue<Stone, vector<Stone>, cmp> pq; for (int i = 0; i < n; ++i) { pq.push(Stone(p[i], d[i], i)); } int step = 1; while(!pq.empty()) { if (step & 0x1) { Stone curStone = pq.top(); pq.pop(); pq.push(Stone(curStone.pos + curStone.dist, curStone.dist, curStone.index)); } else { result = pq.top().pos; pq.pop(); } step++; } return result; } };