题解：SP367 EMPODIA - Empodia

liyancen · 2025-12-04 20:49:41 · 题解

题解报告

考虑框段所满足的性质。可以发现有 a[j]-a[i]=j-i，同时我们又可以发现框段之间不是完全包含就是不相交，不可能存在即相交有包含的情况，因此可以考虑从后往前枚举起点，然后暴力判断重点。

但是这里要注意一个优化，就是我们可以缩短右端点枚举的范围，这样不仅可以降低时间复杂度，还可以保证找到的框段一定是障碍段。

具体实现看代码吧。

#include<bits/stdc++.h>
using namespace std;
const int INF=2e6+10;

int ans,a[INF];
int ans_l[INF],ans_r[INF],ed;
int main(){
    int H;
    cin>>H;
    ed=H;
    for (int i=1;i<=H;i++)cin>>a[i]; 
    for (int i=H;i>=1;i--){//枚举首项 
        int maxn=a[i];
        for (int j=i+1;j<=ed;j++){
            if (a[j]<a[i])break;
            if (a[j]>maxn&&a[j]-a[i]==j-i){
                maxn=a[j];
                ans_l[++ans]=i,ans_r[ans]=j;
                ed=j;
                break;
            }
            maxn=max(maxn,a[j]);
        }
    }
    cout<<ans<<"\n";
    for (int i=1;i<=ans;i++)cout<<ans_l[i]<<" "<<ans_r[i]<<"\n";
    return 0;
}