感受
随手一画,有点难,再看看题目,原来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;
}



京公网安备 11010502036488号