首页 > 代码库 > POJ3069（贪心+巧用优先队列）

POJ3069（贪心+巧用优先队列）

2024-09-02 02:31:51   219人阅读

题目传送门：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（贪心+巧用优先队列）


联系
我们