CF460C Present
2024-09-08 05:23:43
写在前面
- 由于菜,写树状数组写挂了。
- 于是想出了一种不像线段树或树状数组+二分答案那样显然,但是依旧不难想,复杂度比较优秀,代码难度低的做法。
算法思路
外部二分答案,不多解释,稍证明一下单调性:
若把每一次浇水都浇到当前最低的花上,浇水次数越多,花的高度最小值不会变小,满足单调性。
考虑到在某个点被浇的次数只与上一盆水是否为之前某次浇水的终点和这点是否需要继续浇水,以及需要继续浇多少次有关。
那么存一个变量统计当前这个点目前已经被浇了多少次水,设这个变量为 \(x\)。
每当需要浇一次水的时候,假设此时位置是 \(i\),就在 \(i + w\) 的位置打一个数值上等于此次浇水次数相反数的标记。
这样,每当遍历到某个点的时候,先继承上个位置的 \(x\) 并将 \(x\) 加上该点的标记。
再判断 \(a_i + x\) 是否小于二分值 \(lim\),若小于,就浇到这个值,统计次数,打标记。
Tips
- 有的测试点答案很大,二分最大边界开成 \(2\times 10^9\) 足够。
- 如果不特判,标记数组大小要开两倍,不然 \(i + w\) 有会越界。
- 不开
long long
见祖宗。
Code
#include<bits/stdc++.h>
#define LL long long
const int Maxn = 1e5 + 5;
const int Maxm = 1e5;
const LL Maxw = 2e9;
using namespace std;
LL a[Maxn];
LL b[Maxn << 1];
int n, m, w;
bool check(LL lim) {
LL total = 0, nowt = 0;
memset(b, 0, sizeof(b));
for(register int i = 1; i <= n; ++i) {
nowt += b[i];
if(a[i] + nowt < lim) {
LL t = lim - (a[i] + nowt);
total += t;
b[i + w] = -t;
nowt = lim - a[i];
}
}
return total <= m;
}
signed main() {
scanf("%d%d%d", &n, &m, &w);
for(register int i = 1; i <= n; ++i) scanf("%lld", &a[i]);
LL l = 0, r = Maxw, mid, ans = -1;
while(l <= r) {
mid = (l + r) >> 1;
if(check(mid)) {
l = mid + 1;
ans = mid;
}
else {
r = mid - 1;
}
}
printf("%lld", ans);
return 0;
}
最新文章
- py2exe使用中遇到的几个问题
- Tomcat:基于HTTP协议的Connector配置
- iOS设置圆角矩形和阴影效果
- java使用poi读取ppt文件和poi读取excel、word示例
- 升级PHP
- 第十二章 非对称加密算法-RSA
- ORACLE PL/SQL编程详解
- Ubuntu Geany中文乱码
- Color Cube – 国产的优秀配色取色工具
- 转:MySQL导入.sql文件及常用命令
- C复习手记(Day3)
- linux 下一个 jira-6.3.6 组态 皴 翻译 迁移数据库
- Uva 10892 LCM Cardinality (数论/暴力)
- Highway LSTM 学习笔记
- SystemTap Beginners Guide
- 极光推送JAVA代码示例
- Dear Menuhin
- shell下获取系统时间
- Java匿名内部类的继承者、终结者————lambda表达式
- python基础学习1-面向对象
热门文章
- orcl数据库自定义函数--金额小写转大写
- Putty或MobaXTerm无法连接VMware虚拟机 报Network error: Connection timed out的解决方案
- 免费的java代码混淆,程序加密
- 最全Java面试题(一)
- Servlet[JAX-RS Servlet]的Servlet.init()引发异常
- ORA-28001: the password has expired解决方法
- Go语言从入门到放弃(四)
- 利用GPU实现大规模动画角色的渲染(转)
- 基于 MPI/OpenMP 混合编程的大规模多体(N-Body)问题仿真实验
- java8 stream api流式编程