考虑到不管怎么走,都是 \(0\) 最后又绕回 \(0\),于是答案肯定是 \(2L\) 的倍数。
那么考虑 \(\frac{\operatorname{ans}}{2L}\) 即可。
那么对于 \(t_i\),可以先让答案加上 \(\lfloor\frac{t_i}{2L}\rfloor\),同时令 \(t_i\leftarrow t_i \bmod 2L\)。
原因就是考虑到这被去除掉的 \(2L\) 肯定是转的完整的一圈,没有什么影响。
那么剩下的 \(t_i\) 就满足 \(t_i\in [0, 2L)\) 了。
接下来考虑对于这部分 \(t_i\) 怎么做。
首先有一个很显然的上界,从左往右,对于每个 \(i\) 都转一圈,那么一共就有 \(n\) 圈,还加上 \(0\) 到 \(0\) 的 \(1\) 圈,共 \(n + 1\) 圈。
考虑从这个上界往下减小。
首先如果有 \(t_i = 0\),明显不用多转一圈了,就可以 \(-1\)。
接下来考虑到其实转一圈有点浪费,可能转不满一圈那就肯定贪心的不会让其转满。
于是令 \(l_i, r_i\) 分别代表对于 \(i\) 能不能从左边 / 右边进入且出来时朝着这个方向,用式子表示就是 \(l_i = [2(L - x_i)\ge t_i], r_i = [2x_i\ge t_i]\),可能式子还清晰一些。
那么对于 \(n\),因为其是最后一个,那么若 \(l_n = 1\),那么就不用多转一圈了,就可以 \(-1\)。
同时对于 \(1\le i < j < n, r_i = 1, l_j = 1\),那就可以考虑先不走 \(i\),而是先走过 \(j\) 再走 \(i\) 绕回来,能发现这样子同样是 \(1\) 圈却走完了 \(2\) 个,也可以 \(-1\)。
那么接下来就解决这种情况。
首先 \((l_i, r_i) = (0 / 1, 0 / 1)\),对于 \((0, 0)\) 没用显然可以直接排除掉。
那么接下来的配对就只有可能是 \(((l_i, r_i), (l_j, r_j)) = ((1, 1), (1, 1)) / ((0, 1), (1, 1)) / ((1, 1), (1, 0)) / ((0, 1), (1, 0))\) 了。
再进一步考虑,能发现若 \((l_i, r_i) = (0, 1)\) 意味着 \(2x_i\ge t_i, 2L - 2x_i < t_i\),就有 \(2x_i\ge t_i, 2x_i > 2L - t_i\),所以 \(2x_i\ge \max\{t_i, 2L - t_i + 1\} = L + 1\);同理,能得到对于 \((l_i, r_i) = (1, 0)\) 有 \(2x_i\le L - 1\)。
那么就可以知道不可能存在 \(i < j, ((l_i, r_i), (l_j, r_j)) = ((0, 1), (1, 0))\) 的情况。
所以就只有前三种情况了。
能发现 \((1, 1)\) 可以算作万能的,所以先去贪心的匹配 \(((0, 1), (1, 1)), ((1, 1), (1, 0))\),最后再处理 \(((1, 1), (1, 1))\) 即可。
时间复杂度 \(\mathcal{O}(n)\)。
#include<bits/stdc++.h>
using ll = long long;
const int maxn = 3e5 + 10;
ll x[maxn], t[maxn];
int l[maxn], r[maxn];
bool vis[maxn];
int main() {
int n; ll L;
scanf("%d%lld", &n, &L);
for (int i = 1; i <= n; i++) scanf("%lld", &x[i]);
for (int i = 1; i <= n; i++) scanf("%lld", &t[i]);
ll ans = n + 1;
for (int i = 1; i <= n; i++)
ans += t[i] / (2 * L), t[i] %= (2 * L);
for (int i = 1; i <= n; i++)
if (! t[i])
vis[i] = 1, ans--;
for (int i = 1; i <= n; i++)
l[i] = (L - x[i]) * 2 >= t[i], r[i] = x[i] * 2 >= t[i];
if (! vis[n])
vis[n] = 1, ans -= l[n];
std::vector<int> id;
for (int i = 1; i < n; i++)
if (! vis[i]) {
if (! l[i] && r[i])
id.push_back(i);
if (l[i] && r[i] && id.size()) {
int j = id.back(); id.pop_back();
vis[i] = vis[j] = 1, ans--;
}
}
id.clear();
for (int i = n - 1; i; i--)
if (! vis[i]) {
if (! r[i] && l[i])
id.push_back(i);
if (l[i] && r[i] && id.size()) {
int j = id.back(); id.pop_back();
vis[i] = vis[j] = 1, ans--;
}
}
for (int i = 1, j = -1; i < n; i++)
if (! vis[i] && l[i] && r[i]) {
if (~ j) vis[i] = vis[j] = 1, j = -1, ans--;
else j = i;
}
printf("%lld\n", ans * 2 * L);
return 0;
}
标签:Atcoder,Shopping,int,2x,vis,AGC022D,&&,2L,id
From: https://www.cnblogs.com/rizynvu/p/18301934