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

· · 题解

题目大意

在数组中找到一个满足特定条件的整数 j ，对于每一个数组中的元素 a_i ,我们需要找到一个 j 使得 1 \le i+j \le n 且 a_i \le j \le a_{i+j}。

如果找到符合条件的 j ，则输出 1 和 j ，否则输出 0。

解题思路

  1. 初始化 maxn 数组为极小值，用于记录从1到 i 位置之间满足条件的最大的 i 的值。
  2. 用 ans 数组记录满足 a_i \le j \le a_{i+j} 的 j 的位置。
  3. 计算答案，判断后进行输出。

    参考代码

#include<bits/stdc++.h>
using namespace std; 
#define int long long 
int n; 
const int N=3e5+7;
int ans[N], maxn[N],a[N]; 
signed main()
{ 
    cin >> n; 
    for(int i=1;i<=n;i++)
    { 
        cin >> a[i]; 
        maxn[i] = -1e18; // 初始化maxn数组 
    }
    for(int i=1;i<=n;i++)
    { 
        ans[i] = i - a[i]; // 计算ans[i]，表示满足a[i] <= j <= a[i+j]的j的最小可能位置（i+j的左边界）  
        ans[i] = max(ans[i],1ll); 
        ans[i] = min(ans[i],n + 1); // 确保ans[i]不大于n+1（因为i+j最大为n）  
        maxn[ans[i]] = max(maxn[ans[i]],i); 
    }  
    for(int i=2;i<=n;i++){ // 更新maxn数组，使得maxn[i]存储从1到i位置之间满足条件的最大i值  
        maxn[i] = max(maxn[i],maxn[i-1]);  
    }  
    for(int i=1;i<=n;i++){ 
        int ans1 = maxn[i] - i; // 计算j的值（即满足条件的最大i值减去当前位置i）  
        if(a[i] <= ans1) cout << "1 " << ans1 << "\n"; // 如果a[i] <= ans，说明找到了满足条件的j，输出1和j的值  
        else cout << "0" <<"\n"; // 否则，输出0，表示没有找到满足条件的j  
    }  
    return 0; //不要忘 
}

时间复杂度

时间复杂度为O(N)，可以通过本题。