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分?