给定数组 p 代表 n 个石头的位置和数组 d 代表这 n 块石头能够扔的距离。
从左(0位置)往右走。当你第 k 次碰到一个石头时,
如果 k 是奇数, 把这个石头往右扔;
如果 k 是偶数,跳过这个石头。
返回不再会碰到石头时,最右边的石头的位置。
样例 1:
输入: p = [1, 2], d = [5, 4]
输出: 11
解释:
一开始,位置1上的石头扔到位置6。
然后跳过位置2的石头。
接着位置6的时候被扔到位置11。
最后跳过位置11的石头。
样例 2:
输入: p = [1, 6], d = [5, 6]
输出: 12
解释:
一开始,位置1上的石头扔到位置6。
然后跳过位置6的石头(更大的石头)。
接着位置6的时候被扔到位置12。
最后跳过位置12的石头。
注意事项
n <= 10^4
p[i] <= 10^5
d[i] <= 10^3
如果两个或多个石头停留在相同位置,
你先碰到的是最大的石头(即 **d[i] 最小**的石头)。
意味着首先扔或跳过较大的石头。
2. 解题
unordered_map m;// 序号idx,石头能扔的dis距离
struct cmp
{
bool operator()(const auto& a,const auto& b)
{
if(a.second == b.second)//距离一样,小的先出队
return m[a.first] > m[b.first];
return a.second > b.second;//距离近的先出队
}
};
class Solution {
public:
int getDistance(vector &p, vector &d) {
if(p.size() == 0)
return 0;
bool flag = true;
priority_queue<pair,vector<pair>,cmp> q;
// pair :序号 idx, 石头位置
for(int i = 0; i < p.size(); ++i)
{
m[i] = d[i];// idx,能扔的dis
q.push(make_pair(i, p[i]));//初始位置
}
pair tp;
while(!q.empty())
{
tp = q.top();
q.pop();
if(flag)
{
q.push(make_pair(tp.first, tp.second+m[tp.first]));
}
flag = !flag;//奇偶交替
}
return tp.second;
}
};
100% 数据通过测试
总耗时 100 ms
您的提交打败了 46.88% 的提交!