急急急!!!

学术版

Chenyuze24 @ 2025-01-11 14:21:30

小龙虾有一个由 n 个正整数组成的序列 {a₁, a₂,..., aₙ},其中 2 ≤ n ≤ 10⁶ 且 1 ≤ aᵢ ≤ n。 对于序列的所有区间 [i, j](1 ≤ i < j ≤ n),定义两个函数 c(i, j) 和 d(i, j): c(i, j) 的定义: 若 aᵢ = aⱼ,则 c(i, j) 等于区间 [i, j] 中比两端(即 aᵢ)大的元素的个数。 若 aᵢ ≠ aⱼ,则 c(i, j) = 0。 d(i, j) 的定义: 若区间 [i, j] 的长度(即 j - i + 1)是奇数,则 d(i, j) = 1。 若区间 [i, j] 的长度是偶数,则 d(i, j) = 2。 要求计算序列 a 中所有区间的 c(i, j) × d(i, j) 之和。 输入描述 第一行输入一个整数 n,表示序列中的元素个数。 第二行输入 n 个整数 a₁, a₂,..., aₙ,表示序列中的元素。 输出描述 在一行中输出一个整数,代表所有 c(i, j) × d(i, j) 之和。 示例 1 输入:

6 1 1 4 5 1 4 输出:

8 说明:

在这个样例中,除 c(1, 5) = 2、c(2, 5) = 2、c(3, 6) = 1 外,其余 c(i, j) 均为 0。 对于非零的 c(i, j),d(1, 5) = 1、d(2, 5) = 2、d(3, 6) = 2。 最终计算结果为 2×1 + 2×2 + 1×2 = 8。 数据范围与提示

对于40 % 的数据,n ≤ 1000.

对于另外 100 % 的数据,n ≤ 100000.

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<int, vector<int>> pos;
    for (int i = 0; i < n; i++) {
        pos[a[i]].push_back(i);
    }

    long long result = 0;

    for (auto& entry : pos) {
        vector<int>& indices = entry.second; 
        int m = indices.size();             

        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                int l = indices[i];
                int r = indices[j];

                int count_larger = 0;
                for (int k = l + 1; k < r; k++) {
                    if (a[k] > a[l]) {
                        count_larger++;
                    }
                }

                int len = r - l + 1;
                int d = (len % 2 == 1) ? 1 : 2; 
                result += count_larger * d;
            }
        }
    }

    cout << result << endl;

    return 0;
}

这怎么0分?


|