对于一道站外题（难度大概csps T2)

题目描述 今天 syy 和同学们一起出去春游，正准备回学校时，班主任临时告诉 syy 希望他可以给全班同学拍一个合照

班级里总共有 n n 个同学从左往右排成一队，每个同学有自己的身高，第 i i 个同学的身高为 a i a i ​

一般合照要好看的话都是在中间形成一个峰：类似于 [ 1 , 2 , 3 , 2 , 1 ] [1,2,3,2,1] 这种形式，但是来接的大巴车马上就要到了，看着随意排成一队的同学们，再重新排队肯定是来不及了！

于是 syy 决定不让同学们再移动了，他可以将现在的队伍分成前中后三段，各拍一张照片。

其中第一张照片和最后一张照片中身高最高的同学身高，刚好等于中间这张照片中身高最矮的同学身高。

若能够拍出这样的照片， syy 就可以用软件合成出一张完美的合照。

当然，在拍照时不能漏下班里任何一个同学。

现在时间紧急，syy 只能向你求助，请你帮他计算一下他能否拍出这样的照片，若能，则告诉他从左往右三张照片中分别有多少人。

输入格式 输入第一行为一个正整数 T

T 表示有多少组测试数据

对于每组测试数据满足：

输入第一行包含一个正整数 n

n 表示有多少同学

输入第二行包含 n 个正整数

a 1 , a 2 . . . a n a 1 ​ ,a 2 ​ ...a n ​

分别表示每个同学的身高 输出格式 对于每组测试数据：

第一行输出 YES 或者 NO 表示能否拍出这样的照片

若第一行输出为 YES，则在第二行输出三个正整数分别表示从左往右每张照片中的人数，若存在多种方案，输出字典序最小的那一组。

输出的 YES 和 NO 不包含引号

t<=1000

3<=n<300000

ai<=1000000000```cpp #include<bits/stdc++.h> using namespace std; int t,n,a[500001],pre[500001],suf[500001],min2; //(i)类情况返回1 //（ii）类情况返回2 //(iii)返回3 //(iiii)返回4

//思路：枚举第一个分割点，二分第二个分割点 //(i)如果1的最大值小于2的最小值，让2的最小值更小，l=mid+1 //(ii)如果1的最大值大于2的最小值，让2的最小值更大，r=mid-1 //(iii)如果1的最大值大于3的最大值，让3的最大值更大，r=mid-1 //（iiii）如果1的最大值小于3的最大值,让3 的最大值小，l=mid+1 int check(int div1,int div2){ int maxn1=pre[div1],minn2=INT_MAX,maxn3=suf[div2]; for(int i=div1+1;i<div2;i++){ minn2=min(minn2,a[i]); } min2=minn2; if(maxn1<minn2){ return 1; } if(maxn1>minn2){ return 2; } if(maxn1>maxn3){ return 3; } if(maxn1<maxn3){ return 4; }

} int main(){ cin>>t; for(int p=1;p<=t;p++){ cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; pre[i]=pre[i-1]; pre[i]=max(pre[i],a[i]); } for(int l=n;l>=1;l--){ suf[l]=suf[l+1]; suf[l]=max(suf[l],a[l]); } } //思路：枚举第一个分割点，二分第二个分割点 //(i)如果1的最大值小于2的最小值，让2的最小值更小，l=mid+1 //(ii)如果1的最大值大于2的最小值，让2的最小值更大，r=mid-1 //(iii)如果1的最大值大于3的最大值，让3的最大值更大，r=mid-1 //（iiii）如果1的最大值小于3的最大值,让3 的最大值小，l=mid+1 for(int i=1;i<=n;i++){ int l=i+1,r=n,mid; while(l<=r){ mid=(l+r)/2; if(check(i,mid)==1){ l=mid+1; } if(check(i,mid)==2){ r=mid-1; } if(check(i,mid)==3){ r=mid-1; } if(check(i,mid)==4){ l=mid+1; } } if(pre[i]==suf[mid]&&pre[i]==min2){ cout<<i<<mid-i<<n-mid; return 0; } } return 0; }

求条