At Least Average
时间限制: 1 Sec 内存限制: 128 MB
题目描述
Blake plays a video game that has n levels. On each level, she can earn in between 0 and 10 points, inclusive. The number of points she gets on a level must be an integer. She has set up a goal for herself to equal or beat a particular average. In order to make her performance seem impressive, she's decided that she wants to count the number of intervals (sets of consecutive levels) where she's equaled or beaten her target average.
We define an interval [i, j], with 1 ≤ i ≤ j ≤ n, to be each level starting at level i and ending at level j, including level j. For example, if Blake played 5 levels with her scores being 5, 1, 2, 4 and 6, and Blake's target average was 3, then here are the following intervals where she equaled or beat her target average:
[1, 1] with average 5
[1, 2] with average 3
[1, 4] with average 3
[1, 5] with average 3.6
[2, 5] with average 3.25
[3, 4] with average 3
[3, 5] with average 4
[4, 4] with average 4
[4, 5] with average 5
[5, 5] with average 6
Blake can make the impressive statement that on 10 intervals her average score was 3 or more.
The Problem
Given the number of levels Blake has played in her video game, her scores on each level, and the average value she'd like to equal or beat, determine the number of intervals that she equaled or beat the given average.
输入
The first line of input will consist of a single positive integer, v (v ≤ 10), representing the number of input cases to process. Input for each case follows, one case taking two lines. The first line of input for each case contains two positive integers, n (n ≤ 100000), and a (a ≤ 10), separated by spaces, representing the number of levels of the video game and the average Blake wants to obtain, respectively. The following line contains n space separated integers, each in between 0 and 10 inclusive, representing Blake's score on each of the n levels, in order.
输出
For each input case, output a single integer on a line by itself representing the number of intervals where Blake obtained her desired average or higher.
样例输入
|
1 2 3 4 5 |
2 5 3 5 1 2 4 6 9 6 10 1 10 1 10 1 10 1 10 |
样例输出
|
1 2 |
10 15 |
题解
题目大意：给定一个长度为n的序列，求序列中平均值大于等于a的子区间的个数。
假设有一个长度为n的序列g，对序列的每个数g[i]做减去a的处理，这样大于a的数还是个正数，小于a的数变成了负数，然后对g[]做一遍前缀和得到sum[]。这样处理之后找平均值大于等于a区间的问题就变成了找区间和大于等于0的问题。如果对于区间[i,j]的区间和大于等于0，则sum[j]-sum[i-1]>=0。然后可以通过离散化+树状数组去计数符合sum[j]<=sum[i] (j<i)的j的个数f[i]。最终结果就是\(ans=\Sigma_{i=1}^{n}f[i]+(sum[i]>=0)\)。
代码
|
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 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 1000009; int t[N], n, k, a[N], b[N], m; typedef long long LL; int lowbit(int x) { return x & -x; } int add(int x, int v) { while(x<=m) { t[x] += v; x += lowbit(x); } return 0; } int ask(int x) { int sum = 0; while(x) { sum += t[x]; x -= lowbit(x); } return sum; } int main() { int T; scanf("%d", &T); while(T--) { scanf("%d%d", &n, &k); memset(t, 0, sizeof(t)); for(int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] -= k, a[i] += a[i-1], b[i] = a[i]; sort(b+1, b+n+1); m = unique(b+1, b+n+1)-b-1; LL ans = 0; for(int i = 1; i <= n; i++) { int x = lower_bound(b+1, b+m+1, a[i])-b; ans += 1LL * ask(x); add(x, 1); ans += 1LL * (a[i]>=0); } printf("%lld\n", ans); } return 0; } |
叨叨几句... NOTHING