当前位置: 首页 > news >正文

CF506C Mr. Kitayuta vs. Bamboos 51nod1457 小K vs. 竹子 题目分析

题目概述

小K的花园种着n颗竹子(竹子是一种茎部中空并且长得又高又快的热带植物)。此时,花园中第i颗竹子的高度是hi米,并且在每天结束的时候它生长ai米。

  实际上,小K十分讨厌这些竹子。他曾经试图去砍光它们,但由于竹子的茎部太坚固而失败了,然而,小K制作了魔法锤使这些竹子只能在地面上生长。

  由于魔法力量有限,他每天最多能使用K次魔法锤。每次他使用魔法锤敲击竹子,竹子的高度就会减少p米。通过这次改变,如果竹子的高度变为负数,那它转而会变为0米(但它不会消失)。换言之,如果一颗被魔法锤敲击的竹子的高度是h,那它的新高度将会是max(0, h - p)米。我们可以在一天中多次敲击同一颗竹子。

  小K将会从今天开始和这些竹子抗战m天。他的目标是在m天后使其中最高的竹子的高度最小化(即,“小K敲击竹子,然后竹子生长”的m次迭代)。找出m天后,最高的竹子的高度的最小可能值。

 Input
输入的第一行包含四个以空格隔开的整数n,m,k和p(1 ≤ n ≤ 10^5 ,1 ≤ m ≤ 5000, 1 ≤k≤ 10, 1 ≤ p ≤ 10^9)。它们分别表示小K 花园中的竹子数,小K抗战的持续天数,每天小K能敲击竹子的最多次数和魔法锤的力量。
接下来n行描述了竹子的特性,第i行(1 ≤ i ≤ n) 包含两个以空格隔开的整数hi和ai,(0 ≤ hi ≤ 10^9, 1 ≤ ai ≤ 10^9),分别表示第i颗竹子的初始高度和生长速率。
Output
输出m天后,最高的竹子的高度的最小可能值。

分析

神仙。

教练说布置的蓝题绿题作业,CF*2900,666666。。。。。。。

好了步入正题。

显然二分答案,考虑发现正着做很难(我想不出来),考虑倒着做。

也就是说,一开始的竹子都是 \(mid\) 的高度,那么每过一天,竹子就会下降一个值,你需要每天用 \(k\) 次机会将它拉高 \(p\) 个单位。

我们需要保证这整个过程中不能出现负数。

为什么,出现负数说明按照你这个方案最后会使得他大于当前的 \(mid\),会使得不合法。

这种转换的方式巧妙之处在于没有了砍成负数变为 \(0\) 的限制,就很舒服。

如果存在竹子再过一些天高度就变负数的话,就用在变负天数最少的竹子上。不然就用在最后和实际初始高度差最大的竹子上。用个堆维护一下当前编号、长度、还有几天即可。

代码

时间复杂度 \(\mathcal{O}(mk\log A\log n)\)

#include <iostream>
#include <cstdio>
#include <stdlib.h>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
#define int long long
#define N 100005
int n,m,k,p;
struct node{int len,delta;
}a[N],b[N];
struct hep{int id,h,tim;bool operator<(const hep&adv) const {return tim > adv.tim;}
};
priority_queue<hep> q;
bool check(int bz) {while(!q.empty()) q.pop();for (int i = 1;i <= n;i ++)if (bz < a[i].delta * m + a[i].len)q.push({i,bz,bz / a[i].delta + 1});for (int i = 1;i <= m && !q.empty();i ++) {for (int j = 1;j <= k && !q.empty();j ++) {auto now = q.top();q.pop();if (now.tim <= i) return 0;now.h += p,now.tim = now.h / a[now.id].delta + 1;if (now.h < a[now.id].delta * m + a[now.id].len) q.push(now);}}return q.empty();
}
signed main(){cin >> n >> m >> k >> p;int l = 0,r = 0;for (int i = 1;i <= n;i ++) scanf("%lld%lld",&a[i].len,&a[i].delta),l = max(l,a[i].delta),r = max(r,a[i].delta * m + a[i].len);int res = r;while(l <= r) {int mid = l + r >> 1;if (check(mid)) res = mid,r = mid - 1;else l = mid + 1;}cout << res;return 0;
}
http://www.hskmm.com/?act=detail&tid=21091

相关文章:

  • 北京 意大利 硕士学签/D签 vfs代办 材料清单
  • temp
  • 我有园子了
  • 使用 Jenkins 的流水线方案实施 CI/CD
  • 加密的病例单
  • 详细介绍:视频融合平台EasyCVR构筑智慧交通可视化管理与智能决策中枢
  • docker 在x86上build arm 镜像
  • 9.29软工
  • 不一样的.NET烟火,基于Roslyn的开源代码生成器
  • 复刻江协旋钮控制模块
  • 告别硬编码!5个让Web自动化脚本更稳定的定位策略
  • 从零开始,使用Idea工具搭建一个springboot项目
  • 最优/极值问题的算法选择
  • 第三方控件库的添加和使用
  • C4NR PVP服务器1.2 天穹炮塔更新
  • 树形dp [JOI Open 2020] 发电站 / Power Plant
  • 深入解析:灵画-AI绘画小程序
  • AT_arc156_b [ARC156B] Mex on Blackboard
  • 产品排序
  • 环形链表II-leetcode
  • ubuntu20.04安装nvidia显卡
  • [线段树系列 #6] 标记永久化
  • 9.29
  • c语言switch和if语句
  • Qt(制作一个方便的文本编辑器)
  • Java EE初阶启程记05---线程安全 - 指南
  • DataGridView表格控件使用说明
  • 题解:P7126 [Ynoi2008] rdCcot
  • 个人微信机器人开发api接口
  • MyBatis技术详解:从入门到高效开发 - 详解