艾灸条,世界末日大逃亡,寒露洗清秋txt
题目链接
很nice的决策单调性题目
首先把给出的式子移项，我们要求的$p_i = max(a_j + \sqrt{|i - j|}) - a_i$。
按套路把绝对值拆掉，$p_i = max(max_{j = 1}^i (a_j = \sqrt{i - j}), max_{j = i + 1}^n (a_j + \sqrt{j - i})) - a_i$
对于后面的一段，我们把序列翻转之后和前一段是等价的。
也就是说，我们现在只需要找到$p_i = max_{j = 1}^i (a_j + \sqrt{i - j})$
考虑到式子中只有一个max函数，那这玩意儿应该是有决策单调性的
直接设$f_j = a_j + \sqrt{i - j}, i \geqslant j$，其中$i$是自变量
观察这个函数，应该是一个在$[j, inf]$内有定义，过点$(j, a[j])$的函数，且增速与函数$g_i = \sqrt{i}$相同
我们需要做的，就是对每个$i$，找到最大的$f_j$
考虑到$g_i$增长速度会越来越慢，所以一个函数增长到一定程度后可能会被另一个函数取代
直接用单调队列维护，设$k_{i, j}$表示$f_i, f_j$的交点，$h, t$分别表示队首/尾，
当新加入一个元素$i$的时候，显然，若$k_{t -1, t} > k_{t - 1, i}$，那么$t$这个函数是没用的、
当$k_{h, h+1} < i$的时候，弹出队首
就是最后输出答案的时候有点“卡精度”，真恶心
经验：
以后看到$f_i = max(f_j) + g$的式子一定要往单调性上想，如果单调性不是很显然的话可以用换元法设函数找单调性
另外绝对值拆开算一般会好算一些
我要评论#include<bits/stdc++.h>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int maxn = 1e6 + 10, inf = 1e9 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int n, a[maxn], q[maxn], cro[maxn];
double p[maxn], sqr[maxn];
double calc(int j, int i) {
return a[j] + sqr[i - j];
}
int k(int x, int y) {
int l = max(x, y), r = n, ans = n + 1;
while(l <= r) {
int mid = l + r >> 1;
if(calc(x, mid) >= calc(y, mid)) l = mid + 1;
else r = mid - 1, ans = mid;
}
return ans;
}
void solve() {
int h = 1, t = 0;
for(int i = 1; i <= n; i++) {
while(h < t && k(q[t - 1], q[t]) >= k(q[t], i)) t--;
q[++t] = i;
while(h < t && k(q[h], q[h + 1]) <= i) h++;
p[i] = max(p[i], calc(q[h], i));
}
}
main() {
n = read();
for(int i = 1; i <= n; i++) a[i] = read(), sqr[i] = sqrt(i);
solve();
reverse(a + 1, a + n + 1);
reverse(p + 1, p + n + 1);
solve();
for(int i = n; i >= 1; i--)
printf("%d\n", max(0, (int)ceil(p[i]) - a[i]));
return 0;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论