是个还行的思维题.跟我昨天出的题差不多.
样例解释:
4
724
57243
5724316
思路找下这个值所在的位子,记录为0,把小于它的计为-1,把大于它的计为1.
然后就是用个map记录,把当前记录为0,因为必须要经过这个点,所以map只能记录前面的数.然后中间的那个数不是太好处理,单独拿出来处理一下.
代码:
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; map<int,int>mp; int a[N]; int b[N]; int main() { int n,t,val,pos,ans=0,sum=0; cin>>n>>t; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); if(a[i]==t) {b[i]=0;val=a[i];pos=i;} } mp[0]=1; for(int i=1;i<=n;i++) { if(a[i]>val) b[i]=1; if(a[i]<val) b[i]=-1; sum+=b[i]; if(i<pos) mp[sum]++; if(i>pos&&mp[sum]) ans+=mp[sum]; }//处理中位数后的数 sum=0; for(int i=pos;i;i--) { sum+=b[i]; if(!sum) ans++; } cout<<ans<<endl; return 0; }