分析
这道题挺不错的,巧妙的运用到了优先队列
首先,因为n个点是确定的,所以我们可以得到n - 1个区间;其次,因为还有k个点是不确定的,所以我们把这k个点依次插入到这n - 1个区间里,在这里我们可以自己定义一个结构体,里面有len和k两个属性,分别代表一个区间的长度和分成的段数,初始化每个区间只有1段;每一次我们从优先队列里取出len / k最大的区间,然后让k++,之后再把它push到队列里,完成k次插入后,取出队列顶部元素,输出len / k即可
参考代码
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
struct Node {
double len, k;
bool operator < (const Node &u) const {
return (this->len / this->k) < (u.len / u.k);
}
};
int n, m, k;
int main() {
while (scanf("%d%d%d", &n, &m, &k) != EOF) {
double l, r;
priority_queue<Node> q;
scanf("%lf", &l); n--;
while (n--) {
scanf("%lf", &r);
q.push((Node){r - l, 1});
l = r;
}
while (k--) {
Node u = q.top(); q.pop();
u.k++; q.push(u);
}
Node u = q.top();
printf("%.1f\n", u.len / u.k);
}
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)