1 条题解
-
0
#include <bits/stdc++.h> using namespace std; int a[110000], s[110000]; map<int, int> ss; int main() { int n, b, p, ans=1; scanf("%d%d", &n, &b); for(int i=1; i<=n; i++) { scanf("%d", &a[i]); if(a[i]==b) a[i]=0, p=i; //等于 b为 0,p记录位置 else a[i]=(a[i]>b)? 1: -1; //比 b大的为 1,比 b小的为 -1 } for(int i=p+1; i<=n; i++) s[i] += s[i-1] + a[i], ss[s[i]]++; // 求右边的前缀和序列 for(int i=p-1; i>=1; i--) { s[i] += s[i+1] + a[i]; // 左边的后缀和序列 int x = s[i] * -1; if(ss.count(x)) ans += ss[x]; //查找是否有相反数 if(s[i] == 0) ans++; //0也是相反数 } if(ss.count(0)) ans += ss[0]; //右边 0的个数 printf("%d\n", ans); return 0; }
- 1
信息
- ID
- 781
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 6
- 标签
- 递交数
- 17
- 已通过
- 12
- 上传者