感受
随手一画,有点难,再看看题目,原来b在数组中只有一个呀!(要是有多个,难度就加大了,主要容易T)
然后,不难,简单模拟即可
思路
假设,那么我们统计一组数据,pos、pos+1、...、n中小与b的个数 - 大于b的个数
对于,答案怎么统计呢?
p枚举pos左边的位置L,记录L到pos中大于b的个数-小与b的个数,然后这个位置对答案的贡献就是之前数据中小与b的个数 - 大于b的个数,而且也保证这是奇数长度。
其实这题目也没啥讲的,就是左边枚举+右边枚举优化即枚举 + 优化
AC代码
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 100000 + 10; map<int, ll> mp; int n, b; int a[maxn]; int main(){ scanf("%d%d", &n, &b); int pos; for(int i = 1; i <= n; i++){ scanf("%d", &a[i]); if(a[i] == b) pos = i; } int num0, num1; num0 = num1 = 0;///num0 表示从pos到这个位置小于4的个数 num1 表示从pos到这个位置大于4的个数 for(int i = pos; i <= n; i++){ if(a[i] > b) num1++; else if(a[i] < b) num0++; mp[num0 - num1]++; } num0 = num1 = 0; ll ans = 0; for(int i = pos; i >= 1; i--){ if(a[i] > b) num1++; else if(a[i] < b) num0++; ans += mp[num1 - num0]; } printf("%lld\n", ans); return 0; }