题目链接
题解
设$b$所在位置是$k$,那么对于$k$及$b$左边的所有位置求一个$d[i]$,表示$i$到$k-1$有几个小于$b$的数。那么对于$k$及其右边的位置$j$我们定义$d[j]$为$k+1$到$j$有几个小于$b$的数,这样对于一个$j$我们想要找到所有的$i$,使得
整理为
用map
实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42
|
#include <cstdlib> #include <algorithm> #include <cstring> #include <map> #define INF 2000000000 using namespace std; typedef long long ll; int (){ int f = 1, x = 0; char c = getchar(); while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar(); } while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar(); return f * x; } map<int, int> mp; int n, a[100005], b, k, ans = 0; void init(){ n = read(), b = read(); for(int i = 1; i <= n; ++i){ a[i] = read(); if(a[i] == b) k = i; } } void solve(){ int cnt = 0; for(int i = k; i >= 1; --i){ if(a[i] < b) cnt++; mp[0 - i - 2 * cnt]++; } cnt = 0; for(int i = k; i <= n; ++i){ if(a[i] < b) cnt++; ans += mp[2 * cnt - i]; } printf("%dn", ans); } int main(){ init(); solve(); return 0; }
|
近期评论