首页 > 代码库 > 编程算法 - 萨鲁曼的军队(Saruman's Army) 代码(C)
编程算法 - 萨鲁曼的军队(Saruman's Army) 代码(C)
萨鲁曼的军队(Saruman‘s Army) 代码(C)
本文地址: http://blog.csdn.net/caroline_wendy
题目: 直线上有N个点, 每个点, 其距离为R以内的区域里, 必须带有标记的点, 本身的距离为0.
尽可能少的加入?标记点, 至少要有多少点被加上标记?
贪心算法, 从最左边的点開始, 依次查找距离为R须要加入?标记的点, 直到结束.
代码:
/* * main.cpp * * Created on: 2014.7.17 * Author: spike */ /*eclipse cdt, gcc 4.8.1*/ #include <stdio.h> #include <limits.h> #include <utility> #include <queue> #include <algorithm> using namespace std; class Program { static const int MAX_N = 10000; int N=6, R=10; int X[MAX_N] = {1, 7, 15, 20, 30, 50}; public: void solve() { sort(X, X+N); int i=0, ans=0; while (i<N) { int s = X[i++]; while (i<N&&X[i]<=s+R) i++; int p = X[i-1]; while (i<N&&X[i]<=p+R) i++; ans++; } printf("result = %d\n", ans); } }; int main(void) { Program P; P.solve(); return 0; }
输出:
result = 3
编程算法 - 萨鲁曼的军队(Saruman's Army) 代码(C)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。