首页 > 代码库 > POJ3069(贪心+巧用优先队列)
POJ3069(贪心+巧用优先队列)
题目传送门:http://poj.org/problem?id=3069
题目大意:一个直线上有N个点。点i的距离是Xi。从这些点中选取若干个加上标记。要求:对于每个点,与其距离为R的范围内必有做标记的点(包括自身)。求至少标记多少点才能满足要求。
题目意思就是让找最少的标记点数,很好理解,贪心嘛,由于最近正在看优先队列,突然感觉这题也能用优先队列做,就实践了一发,也过了;
话不多说上码:
CODE:
1 #include <bits/stdc++.h> 2 3 using namespace std; 4 5 int main() 6 { 7 int r, n, num, num0; 8 priority_queue<int, vector<int>, greater<int> > Q;//优先队列,不过多解释了 9 while(scanf("%d%d",&r, &n) && (r != -1 || n != -1)) 10 { 11 while(!Q.empty()) 12 Q.pop(); 13 for(int i = 0; i < n; i++) 14 { 15 scanf("%d", &num); 16 Q.push(num); 17 } 18 int ans = 0;//最终要输出的答案 19 while(Q.size() > 0) 20 { 21 int mid = Q.top();//此时的mid表示最左边的点 22 while(Q.size() > 0)//这层循环就是找那个要标记的点 23 { 24 if(mid + r >= Q.top()) 25 { 26 num0 = Q.top(); 27 Q.pop(); 28 } 29 else 30 { 31 mid = num0;//此时mid就是要标记的那个点 32 break; 33 } 34 } 35 36 while(Q.size() > 0)//这层循环呢就是找到右边界 37 { 38 if(mid + r >= Q.top()) 39 Q.pop(); 40 else 41 break; 42 } 43 ans++; 44 } 45 printf("%d\n",ans); 46 } 47 return 0; 48 }
虽说用了优先队列,但是没有过多技术成分,个人感觉比较顺手。。。
POJ3069(贪心+巧用优先队列)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。