题解 P3145 【[USACO16OPEN]分割田地Splitting the Field】

2017-10-08 10:58:03


这个是用栈的代码

优点:代码比较短

#include<bits/stdc++.h>
using namespace std;
int n,x,l[1000000],r[1000000],dd,kk,z[1000000],d,ans;
struct lsg{int l,r;}a[1000000];
bool pd(lsg x,lsg y){return x.l<y.l;}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;for (int i=1;i<=n;i++){
        cin>>x;if (x==0){dd=i;continue;}
        if (l[x]){
            r[x]=i;dd=r[x];//找到含有一个元素最左边的和最右边的地方
        }else l[x]=r[x]=i;
    }for (int i=1;i<=n;i++)
        if (l[i])a[++kk].l=l[i],a[kk].r=r[i];
    sort(a+1,a+1+kk,pd);for (int i=1;i<=kk;i++){
        while (a[i].l>a[z[d]].r&&d!=0)d--;
        if (a[i].r>a[z[d]].r&&d!=0){cout<<-1<<endl;return 0;}//处理区间相交情况
        z[++d]=i;ans=max(ans,d);
    }cout<<ans<<endl;
}