萌新求证明 / 证伪神秘贪心
查看原帖
萌新求证明 / 证伪神秘贪心
508032
int08楼主2024/10/13 21:44

solution:

容易将原问题转换为长为 nn 序列,第 ii 位置最大填 xix_i,其它位置的和不超过 yiy_i

贪心是按 yiy_i 排序,答案就是 min(mini=1leaf(xi+yi),mini=2leafj=1iyji1)min(min_{i=1}^{leaf}(x_i+y_i),min_{i=2}^{leaf}\frac{\sum_{j=1}^{i}y_j }{i-1})

不会证明但是 AC 了

2024/10/13 21:44
加载中...