2018-1-23

該題目要求任意一點距離為R的區域內都必須有被標記的點，我們可以將它轉換為 -> 被標記的所有點的所有的R區域內必須要包含所有的點即可。

我們使用的是貪心算法，也就是我們要將被標記的點盡可能的朝右邊去即可，首先我們將他們從左到右進行排序，第一個我們所選取的被標記的點應該是能夠包含掉左邊的點的最靠右的點。。。

假設s是我們還沒有被包含進去的最左邊的點，那么我們要一直往右找到最右邊的那個能夠將這個點包含進去的點；等我們找到了它，我們就將它所能包含進去的點全部跳過，這樣我們就能得到下一個還沒有被包含進去的最左邊的點。

#include<iostream> #include<algorithm> using namespace std;const int N = 1000; int x[N+1]; int r,n;int main(){while (cin>>r>>n){if (r==-1&&n==-1) break;for (int i=0;i<n;i++){cin>>x[i];}sort(x,x+n);int i=0,res=0;while (i<n){int s=x[i++];while (i<n&&x[i]-r<=s) i++;int p=x[i-1];while (i<n&&x[i]<=p+r) i++;res++;}cout<<res<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的poj3069的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。