题目相关

题目链接: 洛谷 P2717 寒假作业

题目背景

zzs 和 zzy 正在被寒假作业折磨，然而他们有答案可以抄啊。

题目描述

他们共有 $n$ 项寒假作业。zzy 给每项寒假作业都定义了一个疲劳值 $a_i$，表示抄这个作业所要花的精力。

zzs 现在想要知道，有多少组连续的寒假作业的疲劳值的平均值不小于 $k$？

简单地说，给定一个长度为 $n$ 的正整数序列 ${a_i}$，求出有多少个连续子序列的平均值不小于 $k$。

输入格式

第一行是两个整数，分别表示序列长度 $n$ 和给定的参数 $k$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

1
2
3
4
3 2
1
2
3

样例输出 #1

1
4

提示

样例 1 解释

共有 $6$ 个连续的子序列，分别是 $(1)$、$(2)$、$(3)$、$(1,2)$、$(2,3)$、$(1,2,3)$，平均值分别为 $1$、$2$、$3$、$1.5$、$2.5$、$2$，其中平均值不小于 $2$ 的共有 $4$ 个。

数据规模与约定

  • 对于 $20%$ 的数据，保证 $n \leq 100$。
  • 对于 $50%$ 的数据，保证 $n \leq 5000$。
  • 对于 $100%$ 的数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i,k \leq 10^4$。

题目解析

平均值不小于 $k$ 等涉及平均除法运算，处理起来比较麻烦，可以对原始数据减去 $k$ 进行处理。

设 $b_i=a_i-k$，那么问题转变为 $b_i$ 有多少连续子序列，其平均值大于等于 $0$，也即和大于等于 $0$。

对于区间和的问题，通常能想到前缀和。设 $s_j=\sum\limits_{i=1}^{j}a_i$，那么问题转变为有多少对 $(i,j),0\le i<j \le n$ 满足 $s_j-s_i\ge 0 \Rightarrow s_i\le s_j$。

可以看出这是一个正序对问题，思路与求解逆序对类似。需要注意相等的情况也要计算在内。

代码

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
56
57
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int maxn = 1e5 + 10;

int n, k;
int a[maxn]; 
long long s[maxn];
long long ans;

long long tmp[maxn]; // for merge sort
void mergeSort(int l, int r) {
    if (r <= l) return; 
    
    int mid = (l + r) >> 1;
    mergeSort(l, mid);
    mergeSort(mid + 1, r);
    int cur_l = l, cur_r = mid + 1, cur = l;
    while (cur_l <= mid && cur_r <= r) {
        if (s[cur_l] <= s[cur_r]) {
            tmp[cur++] = s[cur_l++];
            ans += r - cur_r + 1;
        } else {
            tmp[cur++] = s[cur_r++];
        }
    }
    while (cur_l <= mid) tmp[cur++] = s[cur_l++];
    while (cur_r <= r) tmp[cur++] = s[cur_r++];
    
    for (int i = l; i <= r; ++i) {
        s[i] = tmp[i];
    }
}

int main() {
    // read input
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
    }
    
    // process & get prefix sum
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] -= k;
        s[i] = s[i - 1] + a[i];
    }
    
    // get ordered pairs
    mergeSort(0, n);
    printf("%lld\n", ans);
    
    return 0;
}