毕业设计网站做几个页面,想在微信公众号上做网站链接,百度网址大全首页设为首页,做一个网站的费用构成更好的阅读体验
竹子 题解
赛题来自 OIFHA 第四场模拟赛。
原题展现
青蛙哥种了 n n n 棵竹子#xff0c;一开始第 i i i 棵竹子的高度为 h i h_i hi#xff0c;每天会长高 a i a_i ai。由于竹子长得太快#xff0c;青蛙哥不得不砍掉一些竹子#xff0c;但是一开始第 i i i 棵竹子的高度为 h i h_i hi每天会长高 a i a_i ai。由于竹子长得太快青蛙哥不得不砍掉一些竹子但是每次只能砍下一截长度为 p p p 的竹子而且为了防止刀具磨损青蛙哥每天只能用刀砍 k k k 次。如果一个竹子的高度不足 p p p显然砍完之后高度不能为负数而应该是 0 0 0。
青蛙哥想知道他砍了 m m m 天之后最高的一棵竹子的最低高度是多少。每天先砍竹子砍完后竹子才会生长。
Solution
思考一手根据数据范围先看看二分能不能解决是否可能 m m m 天后竹子的高度都不超过 X X X
因为这个竹子被削减到 0 0 0 之后不可能削减到负数不好做。所以需要转换。
这道题难就难在转换。
考虑将“砍”和“长”的概念反过来一开始竹子的高度都是 X X X每天都会“自然削减” a i a_i ai如果削减到负数就失败否则就可以在所有的竹子中选出 k k k 棵“拔高” p p p。
通过这样的转换后我们可以把一些拔高的机会积攒起来留到以后使用。 m m m 天后看看是否所有的竹子高度都至少为 h i h_i hi决定了是否有可能成功。
这样一来问题就清晰了很多。确定二分可做可以开始考虑 check() 了。
每天都有 k k k 次“拔高”机会如果有竹子今天就要削减到负数就“拔高”这棵竹子没有机会了就不行。多余的机会可以积攒。第 m m m 天后如果一棵竹子的高度 h ′ h hh h′h就要用 ⌈ h ′ − h p ⌉ \lceil \frac{h-h}{p}\rceil ⌈ph′−h⌉ 次机会来补足 h h h 的高度。同上如果没有机会了就失败了。
至于“每棵竹子至多什么时候削减到负数”这个东西可以用数组储存一下。说白了就是记录这棵竹子什么时候寄。 c i ⌊ X a i ⌋ c_i\lfloor \frac{X}{a_i}\rfloor ci⌊aiX⌋
这个式子就不解释了自己思考非常显然。
那么第 i i i 天该“拔高“哪些竹子呢
根据上文得到的 c i c_i ci可以丢进小根堆里。如果堆顶快要寄的竹子在当天就要“拔高”了就开始使用机会次数否则就积攒这些机会次数。
Code
#include bits/stdc.h
using namespace std;#define int long long
#define pii pairint, int
#define ft first
#define sd secondconst int MAXN 1e5 5;int n, m, k, p;
int h[MAXN], a[MAXN], b[MAXN], c[MAXN];bool check(int md) {priority_queuepii, vectorpii, greaterpii q;for (int i 1; i n; i) {b[i] md;c[i] md / a[i];q.push({ c[i], i });}int day 0;for (int i 1; i m; i) {day k;while (!q.empty() q.top().ft i) {int j q.top().sd;q.pop();if (day 0)return 0;--day;b[j] p;c[j] b[j] / a[j];q.push({ c[j], j });}}day k;for (int i 1; i n; i) {int hh b[i] - a[i] * m;if (hh h[i])day - ceil(1.0 * (h[i] - hh) / p);}return day 0;
}signed main() {scanf(%lld%lld%lld%lld, n, m, k, p);for (int i 1; i n; i) scanf(%lld%lld, h[i], a[i]);int l a[1], r a[1] * m h[1];for (int i 2; i n; i) l max(l, a[i]), r max(r, a[i] * m h[i]);int ans -1, mid;while (l r) {mid l r 1;if (check(mid))ans mid, r mid - 1;elsel mid 1;}printf(%lld\n, ans);return 0;
}
