比赛地址

比赛地址

比赛地址

比赛地址

比赛地址

比赛地址

题目传送门

题意

给定一个长度为 $n$ 的序列 $a$，一次操作可以将序列中的某个数 $+1$ 或 $-1$。

定义一个序列的差值为序列的最大值减去最小值得到的数。

求进行至多 $k$ 次操作后序列差值的最小值。

$n\le 10^5,a_i\le 10^9,k\le 10^{14}$

LOJ 6066

题目传送门

题意

有 $n$ 棵树，第 $i$ 棵树高度为 $a_i$。你需要砍掉一些树，砍树规则如下：

1. 只能砍最多 $m$ 棵树。
2. 对于每个 $i\ (1\le i\le n-k+1)$，满足 $[i,i+k-1]$ 中被砍掉的树的数量不超过 $1$。

被砍掉的树的位置的高度都变为 $0$。

求砍树后 $\max\limits_{1\le i\le n-k+1}\sum\limits_{j=i}^{i+k-1} a_j$ 的最小值，即最小化所有长度为 $k$ 的区间的树的高度之和的最大值。

$n\le 10^5,a_i\le 10^9$

题目传送门

题意

有$n$根竹子，竹子$i$初始高度为$h_i$，每天晚上会长高$a_i$。

每天白天，你可以选择$k$根竹子（同一根竹子在同一个白天可以多次选择），把他们的高度减少$p$，若竹子当前高度$-p$后$<0$，则竹子高度变为$0$。

最小化$m$天后最高的竹子的高度。