在线设计签名免费网站,滨州做网站公司,最近时政新闻,宁波seo基础入门1. 题目
给定数组 p 代表 n 个石头的位置和数组 d 代表这 n 块石头能够扔的距离。
从左(0位置)往右走。当你第 k 次碰到一个石头时#xff0c; 如果 k 是奇数#xff0c; 把这个石头往右扔#xff1b; 如果 k 是偶数#xff0c;跳过这个石头。
返回不再会碰到石头时 如果 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_mapint,int 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(vectorint p, vectorint d) {if(p.size() 0)return 0;bool flag true;priority_queuepairint,int,vectorpairint,int,cmp q;// pair 序号 idx, 石头位置for(int i 0; i p.size(); i){m[i] d[i];// idx能扔的disq.push(make_pair(i, p[i]));//初始位置}pairint,int tp;while(!q.empty()){tp q.top();q.pop();if(flag){q.push(make_pair(tp.first, tp.secondm[tp.first]));}flag !flag;//奇偶交替}return tp.second;}
};100% 数据通过测试 总耗时 100 ms 您的提交打败了 46.88% 的提交!
