题解：CF2018B Speedbreaker

hhhqx · 2024-12-11 15:12:24 · 题解

不需要反证法，思路会更顺畅一些？

考虑一个 i 在初始城市左侧，贪心地，钦定初始城市右侧所有 a_j \le a_i 的 j 都比 i 先选。

对于 i，得到最大的 j 满足 a_j \le a_i。

• 如果初始城市在 [i+1,j] 之间，一定是在 j-i+1 时间来到 i。
• 如果初始城市 p 在 [j+1,n] 之间，一定是在 p -i+1 时间来到 i。
• 如果城市城市在 i，显然合法。

所以，对于 i，右侧合法的初始城市是一个区间 [i, ?]。

对于初始城市在左侧，同理，也是一个区间 [?,i]。

两个 ? 都可以直接求，然后就是区间求交问题了。

而且这样做没有任何猜结论的心里负担，写起来一下就写完了。

因为有 sort，所以复杂度 O(n \log n)。

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using PII = pair<int, int>;

const int MAXN = 2e5 + 3;

int n, a[MAXN], p[MAXN];
int e[MAXN][2];
bool vis[MAXN];

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int T; cin >> T;
    while(T--){
        cin >> n;
        for(int i = 1; i <= n; i++){
            cin >> a[i], p[i] = i;
        }
        sort(p + 1, p + 1 + n, [](int i, int j){ return a[i] < a[j]; });
        for(int i = 1, j = 1, L = n+1, R = 0; i <= n; i++){
            while(j <= n && a[p[j]] <= a[p[i]]) L = min(L, p[j]), R = max(R, p[j]), j++;
            int x = p[i];
            if(R - L + 1 <= a[x]) e[x][0] = min(n, x + a[x] - 1);
            else e[x][0] = x;

            if(R - L + 1 <= a[x]) e[x][1] = max(1, x - a[x] + 1);
            else e[x][1] = x;

        }
        for(int i = 1; i <= n; i++) vis[i] = 0;
        for(int i = 1, R = n; i <= n; i++){
            R = min(R, e[i][0]);
            if(R < i) break;
            vis[i] = 1;
        }
        int ans = 0;
        for(int i = n, L = 1; i >= 1; i--){
            L = max(L, e[i][1]);
            if(L > i) break;
            ans += vis[i];
        }
        cout << ans << "\n";
    }
    return 0;
}