UVA1260 题解

Lonely_Peak · 2025-04-27 19:44:29 · 题解

题目大意

给定每天的销售额列表 A，对第 i 天（i≥2），计算之前所有天数中销售额小于或等于 A_i 的天数，存入 B_{i-1}。求所有 B_i 的总和。

输入有多个测试用例，每个用例给出 n 和 A 数组。输出每个用例的B数组总和。其中 n≤1000，A_i≤5000。

AC 方法 1——暴力

因为这道题的数据范围实在是太弱了，导致 O(T·n^2) 的代码也能过。所以只需要暴力枚举枚举所有 a_k\leq a_i 的情况并统计就行了。

参考代码

#include<bits/stdc++.h>
#define int long long
#define Rint register int
#define fast_running ios::sync_with_stdio(false),std::cin.tie(0),std::cout.tie(0)
using namespace std;
int a[1005];
signed main() {
    fast_running;
    int T;
    cin >> T;
    while (T--) {
        int n, ans = 0;
        cin >> n;
        for (Rint i = 1; i <= n; i++) cin >> a[i];
        for (Rint i = 2; i <= n; i++) {
            for (Rint k = 1; k < i; k++) {
                if (a[k] <= a[i]) ++ans;
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

AC 方法 2——树状数组

方法 1 实在是过于暴力了，虽然 AC 这道题不难，但要是遇到范围稍微大一点的类似的题，那该如何？

我们可以使用树状数组或线段树维护前缀和的方法，将查询和更新的时间复杂度降为 O(T·n·\log M)，其中 M 是数值的最大值。那么给如何做呢？这里我们将对树状数组进行详解

首先我们要了解树状数组的作用：

动态单点更新 update(x, 1)：记录数值 x 的出现次数。
前缀和查询 query(x)：查询 ≤ x 的元素个数。

树状数组的实现

int BIT[5005]; // 树状数组，A[i] ≤ 5000

// 更新：在位置x增加val
void update(int x, int val) {
    for (; x <= 5000; x += x & -x)
        BIT[x] += val;
}

// 查询：统计 ≤x 的元素个数
int query(int x) {
    int res = 0;
    for (; x > 0; x -= x & -x)
        res += BIT[x];
    return res;
}

x & -x：获取 x 的二进制最低位的 1（如 6\ \& -6 = 2）。
update(x, 1)：表示数值 x 出现了一次。
query(x)：返回 ≤ x 的元素总数。

主逻辑

int sum = 0;
memset(BIT, 0, sizeof(BIT)); // 初始化树状数组

for (int i = 1; i <= n; i++) {
    if (i > 1) {
        sum += query(A[i]); // 查询 ≤A[i] 的个数
    }
    update(A[i], 1); // 将 A[i] 加入树状数组
}

对 i ≥ 2，查询 ≤ A_{i} 的元素个数（query(A[i])），并累加到 sum。
更新树状数组，记录 A_{i} 的出现次数（update(A[i], 1)）。

完整代码

#include <bits/stdc++.h>
using namespace std;

int BIT[5005];

void update(int x, int val) {
    for (; x <= 5000; x += x & -x)
        BIT[x] += val;
}

int query(int x) {
    int res = 0;
    for (; x > 0; x -= x & -x)
        res += BIT[x];
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, sum = 0;
        cin >> n;
        memset(BIT, 0, sizeof(BIT));

        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x;
            if (i > 1) {
                sum += query(x);
            }
            update(x, 1);
        }
        cout << sum << '\n';
    }
    return 0;
}