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

这个是用栈的代码 优点：代码比较短 ```cpp #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; } ```