首页 > 代码库 > POJ3069-Saruman's Army
POJ3069-Saruman's Army
直线上有N个点，点i的位置是Xi。从这N个点中选择若干个点，给它们加上标记。对每个点，其距离R内的区域里必须有带有标记的点（自己本身带有标记的点，可以认为与其距离为0的地方有一个带有标记的点）。在满足这样的条件下，至少多少个点被加上标记。
从最左边的点开始，距离为R以内的最远的点，加上第一个标记后，剩下的部分也用同样的办法处理。对于添加了符号的点右侧相距超过R的下一个点，采用同样的方法找到其右侧R距离以内最远的点添加标记。在所有的点被覆盖之前不断的重复这一过程。
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 5 int N, R; 6 int X[1200]; 7 8 void solve() 9 {10 sort(X, X+N);11 int i = 0, ans = 0;12 13 while (i < N)14 {15 //s是没有被覆盖的最左的点的位置16 int s = X[i++];17 //一直向右前进直到距s的距离大于R的点18 while (i < N && X[i] <= s+R) i++;19 //p是新加上标记的点的位置20 int p = X[i-1];21 //一直向右前进直到距p的距离大于R的点22 while (i < N && X[i] <= p+R) i++;23 ans++;24 }25 cout << ans << endl;26 }27 28 int main()29 {30 while (cin >> R >> N)31 {32 if (R == -1 && N == -1)33 return -1;34 for (int i = 0; i < N; i++)35 cin >> X[i];36 solve();37 }38 return 0;39 }
POJ3069-Saruman's Army
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。