喷水装置 ACM题目 京东16招聘编程题（贪心算法）

喷水装置 ACM题目 京东16招聘编程题（贪心算法）

描述：现有一块草坪，长为20米，宽为2米，要在横中心线上放置半径为Ri的喷水装置，每个喷水装置的效果都会让以它为中心的半径为实数Ri(0 < Ri < 15)的圆被湿润，这有充足的喷水装置i（1 < i < 600)个，并且一定能把草坪全部湿润，你要做的是：选择尽量少的喷水装置，把整个草坪的全部湿润。 输入：第一行m表示有m组测试数据  每一组测试数据的第一行有一个整数数n，n表示共有n个喷水装置，随后的一行，有n个实数ri，ri表示该喷水装置能覆盖的圆的半径。 输出：输出所用装置的个数 样例输入：

252 3.2 4 4.5 6 101 2 3 1 2 1.2 3 1.1 1 2

样例输出：

25

代码：

#include #include #include #include using namespace std;int main(){ double length = sqrt(20 * 20 + 2 * 2)/2; int k; cin >> k; for (int i = 0; i < k; ++i) { int n; double temp; vector ivec; cin >> n; for (int j = 0; j < n; ++j) { cin >> temp; ivec.push_back(temp); } sort(ivec.begin(), ivec.end()); double sum = 0; int num=0; for (auto r = --ivec.end(); r >= ivec.begin(); --r) { sum += *r; num++; if (sum >= length) break; } cout << num<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。