CF1791G2 Teleporters (Hard Version) 题解
题目大意
题意挺清楚的,给个传送门吧。
分析
比较简单的贪心题,很容易就能看出来是贪心,也很容易就能看出来贪什么。
我没做简单版(Teleporters (Easy Version)),但是我去看了一眼。那个也非常简单,不过提供了一点点思路。虽然提供的东西不多,我还是顺便讲一下吧。
那道题和这道题基本一样,不过传送门只能传到起点,即 \(0\) 号点。所以很容易想到,对于每个点算一下使用当前点的传送器所需要的代价 \(b_i\),$b_i = a_i + $ 该点到 \(0\) 号点的距离,然后贪心用最小的即可。
对于这道题,我们不能这么做,因为对于离 \(0\) 号点远但离 \(n + 1\) 号点近的点,明显跳到 \(n + 1\) 号点再过去更优。
但是我们很容易想到,既然每次(除了第一次)可以从 \(0\) 号点开始,也可以从 \(n + 1\) 号点开始,那么我们可以把使用这个传送器的代价 \(b_i\) 设为 \(a_i + \min((i - 0), (n + 1 - i))\),然后贪心。
所以我们主要考虑的是,怎么排除掉第一次的硬性规定(即必须从 \(0\) 号点开始走)。
题解
我们发现,第一次必须从 \(0\) 号点开始,而且只有这一次有限制。所以我们可以枚举这个点,即枚举第一次使用的传送器。
接着去想怎么找最多能用多少个传送器。
我们发现,即使求出了每一个传送器的代价,并排了序,也不好直接求从头用能用多少个(从头指的是排完序从代价最少的开始用)。
于是前缀和优化一下,\(qian_i\) 表示我用了代价最少的 \(i\) 个传送器所需要的代价,即 \(\displaystyle qian_i = \sum_{j = 1}^i b_j\)。
我们现在的问题就转化成了对于一个 \(c\),怎么去找满足 \(qian_i < c\) 的最大的 \(i\)。
分析到这了,很容易想到二分了吧。
或者你再看看范围 \(2 \times 10^5\),大抵是 \(O(n \log n)\),枚举需要 \(O(n)\),那么我们需要一个 \(O(\log n)\) 左右的算法,而且还是要在序列上找一个位置,也很容易想到二分吧。
但是我懒得写二分,写了个 \(\operatorname{upper\_bound}\)。
但是和二分基本是一样的,都还需要考虑怎么把当前枚举的点对 \(qian\) 数组的影响排除掉。
假设我们当前枚举到了传送器 \(i\)。
我们直接 \(\operatorname{upper\_bound}\) 肯定是不行的,因为我们可能会一个传送器算两次,即枚举到 \(i\),\(i\) 已经用过了,但是 \(\operatorname{upper\_bound}\) 时也有可能包含了 \(i\)。
所以我们先让 \(c\) 减去 \(a_i - i\)(即这个传送器本身的代价与它到 \(0\) 号点的距离之和)再加上 \(b_i\)。这个数的含义就是我们去过第 \(i\) 个传送器后,剩下的金币。用这个数 \(\operatorname{upper\_bound}\) 一次,如果包含了我们枚举的数 \(i\),那么我们就可以直接用这个结果作为当前的答案,与最终的答案 \(ans\) 取个 \(\max\),但是如果没有包含,那么我们用 \(c\) 减去 \(a_i - i\) 再 \(\operatorname{upper\_bound}\) 一次作为当前的答案,与最终答案 \(ans\) 取 \(\max\)。
最后这一小部分属于代码实现了,建议自己静下来想想。代码实现你不看代码光听我口述,听不明白是正常的,我尽力了。
代码
#include <bits/stdc++.h>
#define int long long
#define M 200005
#define P pair<int, int>
#define MP make_pair
using namespace std;
inline int read() {
int x = 0, s = 1;
char ch = getchar();
while(ch < '0' || ch > '9') {
if(ch == '-')
s = -s;
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = (x << 3) + (x << 1) + ch - '0';
ch = getchar();
}
return x * s;
}
void write(int x) {
if(x < 0) {
x = ~(x - 1);
putchar('-');
}
if(x > 9)
write(x / 10);
putchar(x % 10 + 48);
}
int n, T, a[M], c, qian[M], ans, cnt;
P pa[M];
signed main() {
T = read();
for(int t = 1; t <= T; ++ t) {
ans = 0;
n = read();
c = read();
for(int i = 1; i <= n; ++ i) {
a[i] = read();
pa[i] = MP(a[i] + min(i, n + 1 - i), a[i] + i);
}
stable_sort(pa + 1, pa + 1 + n);
for(int i = 1; i <= n; ++ i)
qian[i] = pa[i].first + qian[i - 1];
for(int i = 1; i <= n; ++ i) {
if(c < pa[i].second)
continue;
cnt = upper_bound(qian + 1, qian + 1 + n, c - pa[i].second + pa[i].first) - qian - 1;
if(cnt < i)
cnt = upper_bound(qian + 1, qian + 1 + n, c - pa[i].second) - qian;
ans = max(ans, cnt);
}
write(ans);
putchar('\n');
}
}