#离散#ssl 1747 登山机器人问题

本文主要是介绍#离散#ssl 1747 登山机器人问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

登山机器人可以携带有限的能量。在登山过程中，登山机器人需要消耗一定能量，并且可以在机器人之间通过接触传递能量。计算用这n个登山机器人进行不返回的接力登山可攀登的最高的高度。

---

分析

关键是登山机器人的接力，可以用$x/y^2$来大到小排序，离散后传递能量就搞定了。

---

代码

#include <cstdio>
#include <algorithm>
using namespace std;
struct rec{double a,b,pay;}re[101];
bool cmp(rec x,rec y){return x.pay>y.pay;}
double ans; int n;
int main(){scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%lf",&re[i].a);for (int i=1;i<=n;i++) scanf("%lf",&re[i].b),re[i].pay=re[i].a/(re[i].b*re[i].b);stable_sort(re+1,re+1+n,cmp);for (int i=2;i<=n;i++) re[i].b+=re[i-1].b;for (int i=1;i<=n;i++) ans+=re[i].a/re[i].b;printf("%.2lf",ans);return 0;
}

这篇关于#离散#ssl 1747 登山机器人问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---