hdu 4908 BestCoder Sequence(计数)

本文主要是介绍hdu 4908 BestCoder Sequence(计数)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 4908 BestCoder Sequence

题目大意：给定N和M，N为序列的长度，由1~N组成，求有多少连续的子序列以M为中位数，长度为奇数。

解题思路：v[i]记录的是从1~i这些位置上有多少个数大于M，i-v[i]就是小于M的个数。pos为M在序列中的位置。如果有等式i−j=2∗(v[i]−v[j−1]),i≥pos≥j

那么i和j既是一组满足的情况。将等式变形i−2∗v[i]=j−2∗v[j−1].

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 40000;
int N, M, pos, v[maxn+5], c[2][maxn*2+5];void init () {int a;v[0] = 0;for (int i = 1; i <= N; i++) {v[i] = v[i-1];scanf("%d", &a);if (a > M)v[i]++;if (a == M)pos = i;}
}int solve () {memset(c, 0, sizeof(c));for (int i = 1; i <= pos; i++) {int tmp = i - 2 * v[i-1];c[0][tmp + maxn]++;}for (int i = pos; i <= N; i++) {int tmp = i - 2 * v[i];c[1][tmp + maxn]++;}int ans = 0;for (int i = 0; i <= maxn*2; i++)ans += c[0][i] * c[1][i];return ans;
}int main () {while (scanf("%d%d", &N, &M) == 2) {init();printf("%d\n", solve());}return 0;
}

这篇关于hdu 4908 BestCoder Sequence(计数)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---