我们考虑经典套路,假设前 \(i - 1\) 个数已经被确定。
设 \(f_k(x)\) 表示 \(a_k = x\) 时 \(\sum_{i = k + 1}^n | \ a_i - a_{i - 1} \ |\) 的最小值。
那么,\(a_i = x\) 当且仅当 \(x\) 取最小值且 \(| \ x - a_{i - 1} \ | + f_i(x)\) 为所有可能中的最小值。
我们设集合 \(I_k = \operatorname{argmin}_{x \in [l_k, r_k]} f_k(x)\)。
一个奇妙性质:\(I_k\) 一定是一个区间。
感性理解。容易发现 \(f_k\) 是一个凸函数,所以当取到最小值时,取值定为一个区间。
我们考虑 \(f_k(x)\) 怎么求。
丁真一下。我们可以考虑直接贪心。若 \(a_i = p\),则 \(a_{i + 1}\) 取 \(\operatorname{argmin}_{x \in [l_k, r_k]} | \ x - p \ |\)。然后转移还是比较简单的。
我们设 \(m_k = \min_{x \in [L_k, R_k]}\{f_k(x)\}\):
\[f_k(x) = \begin{cases} m_{k+1} + l_k - x & (x < l_k)\\ m_{k+1} & (x\in [l_k, r_k])\\ m_{k+1} + x - r_k & (r_k < x) \end{cases} \]以上贪心可以通过大力分讨得证。
但是这一眼正确吧。
那么我们观察 \(f_k(x)\) 的转移式,发现最小值是非常能确定的。于是得到下列结论:
- 如果 \([L_k, R_k] \cap I_{k+1} \neq \emptyset\),则 \(I_k = [L_k, R_k] \cap I_{k+1}\)。
- 如果 \(R_k < l_{k + 1}\),则 \(I_k = R_k\)。
- 如果 \(L_k > r_{k + 1}\),则 \(I_k = L_k\)。
综上,我们求出了 \(I\)。\(f\) 实际上不需要求出。
回到原题。我们要找到 \(x\) 使 \(x\) 取最小值且 \(| \ x - a_{i - 1} \ | + f_i(x)\) 为所有可能中的最小值。
仍然是大力分讨:
-
\(a_{i - 1} \in I_i\) 时,\(a_i = a_{i - 1}\)。
-
\(L_i \leq a_{i - 1} < l_i\) 时,\(a_i = a_{i - 1}\)。
-
\(a_{i - 1} < L_i\) 时,\(a_i = l_i\)。
-
\(a_{i - 1} > r_i\) 时,\(a_i = r_i\)。
发现上述过程可以简化为 \(a_i\) 取 \([L_i, r_i]\) 中最靠近 \(a_{i - 1}\) 的值。
以下是代码实现。
#include <bits/stdc++.h>
using namespace std;
long long read() {
char c = getchar();
long long x = 0, p = 1;
while ((c < '0' || c > '9') && c != '-') c = getchar();
if (c == '-') p = -1, c = getchar();
while (c >= '0' && c <= '9')
x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
return x * p;
}
const int N = 5e5 + 7;
int n;
int l[N], r[N], L[N], R[N];
int ans[N];
void solve() {
n = read();
for (int i = 1; i <= n; i ++)
L[i] = read(), R[i] = read();
l[n] = L[n], r[n] = R[n];
for(int i = n - 1; i >= 1; i --) {
if (R[i] < l[i + 1]) {
l[i] = r[i] = R[i];
} else if (L[i] > r[i + 1]) {
l[i] = r[i] = L[i];
} else {
l[i] = max(L[i], l[i + 1]);
r[i] = min(R[i], r[i + 1]);
}
}
ans[1] = l[1];
for(int i = 2; i <= n; i++) {
if (ans[i - 1] >= l[i] && ans[i - 1] <= r[i])
ans[i] = ans[i - 1];
else if (ans[i - 1] >= L[i] && ans[i - 1] < l[i])
ans[i] = ans[i - 1];
else if (ans[i - 1] < L[i])
ans[i] = L[i];
else ans[i] = r[i];
}
for(int i = 1; i <= n; i ++) cout << ans[i] << ' ';
}
signed main() {
int t = 1;
while (t --) solve();
return 0;
}
标签:题解,long,else,最小值,ARC,&&,ans,175,getchar
From: https://www.cnblogs.com/aemmprty/p/18097471