P11157 【MX-X6-T3】さよならワンダーランド题解

Eternal_crystal · 2024-10-04 11:15:20 · 题解

solution

机房大佬的超绝做法@A1234467

不难发现，数组的最大值是最容易得到答案的，那么我们可以将其预处理出来。

但是又不能保证答案都在最大值处，设最大值为 a，最大值位置为 k，如果最大值处不为答案，那么容易发现答案只可能在 [\max(1 - i, a_i), \min(n - i, a)] 中出现。

综上，先判断最大值是否为答案，再扫一遍区间即可，可以证明在随机数据下时间复杂度保证。

code：

#include<bits/stdc++.h>
using namespace std;
const int N = 300005;
int n, a[N], maxx = INT_MIN, pos;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}
int main(){
    n = read();
    for(int i = 1;i <= n;i++){
        a[i] = read();
        if(maxx <= a[i]){maxx = a[i], pos = i;}
    } 
    for(int i = 1; i <= n; ++i) {
        int ans = INT_MIN;
        if(a[i] <= pos - i && pos - i <= maxx) ans = pos - i;
        if(ans == INT_MIN)
            for(int j = std::max(1 - i, a[i]); j <= std::min(n - i, maxx); ++j)
                if(j <= a[i + j]) {ans = j; break;}
        if(ans != INT_MIN) printf("1 %d\n", ans);
        else printf("0\n");
    }
    return 0;
}