T1：外卖
你当然可以通过直接全排列枚举走的顺序通过本题，但那样太麻烦了
其实本题可以分为以下三种情况：
- \(A\) 点在最左侧，那么最短距离 \(=\) 最大值 \(-\) 最小值
- \(A\) 点在最右侧，那么最短距离 \(=\) 最大值 \(-\) 最小值
- \(A\) 点在中间，那么最短距离 \(=\) 最大值 \(-\) 最小值 + \(\min(\) 最大值 \(-A\)，最小值 \(-A)\)
代码实现
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
freopen("take_out.in", "r", stdin);
freopen("take_out.out", "w", stdout);
int a, b, c, d;
cin >> a >> b >> c >> d;
int mn = min(min(a, b), min(c, d));
int mx = max(max(a, b), max(c, d));
ll ans = mx-mn;
if (mn < a and a < mx) ans += min(a-mn, mx-a);
cout << ans << '\n';
return 0;
}
T2：区间问题 I
首先，给定 \(l, r\)，如何快速计算 \(\sum\limits_{i=l}^r a_i^2 - \sum\limits_{i=l}^r a_i -k(r-l+1)\) ?
令 \(f(x) = \sum\limits_{i=1}^x a_i^2 - \sum\limits_{i=1}^x a_i -kx = \sum\limits_{i=1}^x (a_i^2 - a_i - k)\)
那么我们可以发现，\(f(x)\) 是 \(a_i^2 - a_i - k\) 的前缀和，所以原式可以写作 \(f(r) - f(l-1)\)
想要让 \(f(r) - f(l-1)\) 尽可能大，应该最小化 \(f(l-1)\)，因此在计算 \(f(i)\) 时，还需维护 \(mn = \min\limits_{0 \leqslant j \leqslant i-1} f(j)\)，因此答案为 \(\max(f(i)-mn)\) 。
代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
int main() {
freopen("interval.in", "r", stdin);
freopen("interval.out", "w", stdout);
int n, k;
cin >> n >> k;
vector<ll> a(n);
rep(i, n) cin >> a[i];
vector<ll> b(n);
rep(i, n) b[i] = a[i]*a[i] - a[i] - k;
vector<ll> s(n);
rep(i, n) s[i+1] = s[i]+b[i];
ll ans = -1e18, mn = 0;
for (int i = 1; i <= n; ++i) {
ans = max(ans, s[i]-mn);
mn = min(mn, s[i]);
}
cout << ans << '\n';
return 0;
}