AT3527 [ARC082D] Sandglass
解法一
直接考虑在初始为 \(a\) 的情况下时刻 \(t\) 时 \(A\) 中剩余的沙子是行不通的,不妨反过来考虑在时刻 \(t\) 每个初始值 \(a\) 的答案,令其为 \(f_t(a)\)。
因为若一开始 \(A\) 中沙子多之后的任意时刻 \(A\) 中的沙子也会更多,那么我们可以发现:\(f_t(0) \le f_t(1) \le \cdots \le f_t(X)\)。
单独考虑我们现在要求的 \(f_t(a)\),若 \(f_t(a)\) 的函数图像在某一点和 \(f_t(0) / f_t(X)\) 相交那么其接下来的函数图像必然会与 \(f_t(0) / f_t(X)\) 重合。
如果没有相交的话,\(f_t(a)\) 也必然不会与 \(y = X, y = 0\) 相交,此时就不会出现与 \(0\) 取 \(\max\) 或与 \(X\) 取 \(\min\) 的情况了,此时的函数值就可以快速算出了。
于是难点在于如何判断 \(f_t(a)\) 是否与 \(f_t(0), f_t(X)\) 相交。
首先我们先算出如果不相交的函数值 \(g_t(a)\),直觉告诉我们若 \(f_t(0) < g_t(a) < f_t(X)\) 那么没有相交否则越过哪条线就会与哪条线相交。
因为相交处必然在 \(y = 0, y = X\) 上,那么一旦相交就会比 \(f_t(0), f_t(X)\) 慢半拍以至于后面肯定在区间外。
那么我们只需计算出每个查询时刻 \(f_t(0), f_t(X)\) 以及不算相交的值即可,复杂度 \(\mathcal{O(n + m)}\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 1e5 + 5;
int n, q, t, a, k, X, P, buf, f[2], r[N];
int F(int x, int buf) { return max(0ll, min(X, x + buf));}
signed main () {
cin >> X >> n;
rep(i, 1, n) cin >> r[i];
cin >> q, P = 1;
f[0] = 0, f[1] = X;
while (q--) {
cin >> t >> a;
for (; r[P] <= t && P <= n; ++P) {
buf = (P & 1) ? -(r[P] - r[P - 1]) : (r[P] - r[P - 1]);
k += buf;
f[0] = F(f[0], buf), f[1] = F(f[1], buf);
}
buf = (P & 1) ? r[P - 1] - t : t - r[P - 1];
printf("%lld\n", max(F(f[0], buf), min(F(f[1], buf), a + k + buf)));
}
return 0;
}
解法二
首先需要解法一中相交及之前的分析。
接下来你会发现,函数图像一定先是一段与 \(f_t(0)\) 相同,然后是一段斜率为 \(1\) 的线段,接着一段与 \(f_t(X)\) 相同。
并且这一段与 \(f_t(0) / f_t(X)\) 相同的点对于接下来的每个时刻依然会相同,于是我们只需考虑维护出不同的两个拐点以及 \(f_t(0), f_t(X)\) 的函数值即可。
第一步正难则反的思考是十分重要的。
其次,每当我们有了一个新的想法或转化以后一定要将这个想法或转化下的性质挖掘清楚,观察显得尤为重要。
最新文章
- easyui datagrid 动态操作editor 的方法
- JVM监控工具介绍
- 自定义UI集成微信、QQ、微博分享功能
- Json 字符串 转换为 DataTable数据集合
- fontconfig编译出错
- web.xml配置文件
- CodeForces 702 A Maximum Increase (贪心,高效算法)
- 漂亮的自适应宽度的多色彩CSS图片按钮
- 登陆shell与交互式非登陆shell的区别
- 【python之旅】python的基础三
- 查找jar包的站点
- BZOJ 1260: [CQOI2007]涂色paint( 区间dp )
- HUNNU11342:Chemistry(模拟)
- 使用日志记录功能查看PHP扩展的执行过程
- C++读取excel特定行列中的数据
- 1023: [SHOI2008]cactus仙人掌图(DP+单调队列优化)
- Java 第五周总结
- 来了解一下Mysql索引的相关知识:基础概念、性能影响、索引类型、创建原则、注意事项
- 29:ISBN号码
- 【Android】详解Android Activity
热门文章
- Java编程基础
- [源码解析] PyTorch 分布式之弹性训练(6)---监控/容错
- 代码质量管理sonarqube部署使用
- JVM垃圾收集器专题
- vue3+TypeScript+vue-router使用
- 【】JSON介绍
- Zookeeper集群安装Version3.5.1
- 2021 编程语言排行榜出炉!C#年度语言奖
- MongoDB高级应用之高可用方案实战(4)
- Pytest_Hook函数pytest_addoption(parser):定义自己的命令行参数(14-1)