OR162. 链式边权
描述
n个点连成一条链，从左往右依次从1到n编号。相邻点之间有边相连，一共有n-1条边。所有的边从1到n-1编号，第i条边连接了点i和i+1。
第i个点有点权ai，定义第i条边的权重为wi：有多少点对x，y满足在第i条边的左侧（x≤i），y在第i条边的右侧（y>i），且x和y的点权不同。
给出每个点的点权，请求出所有边的边权。
输入描述
第一行输入一个数n。(2≤n≤100000)
第二行输入n个数，a1,a2,…,an (1≤ai≤109)
输出描述
输出n-1个数，依次为每条边的权重，不要在行末输出多余的空格。示例1
输入:
3 1 2 1
输出:
1 1
C++ 解法, 执行用时: 55ms, 内存消耗: 10012KB, 提交时间: 2020-10-31
#include <cstdio>
#include <unordered_map>
using namespace std;
int nums[100005];
void solve(int n) {
long long pre = 0;
unordered_map<int, int> left, rite;
for (int i = n - 1; i >= 0; --i)
rite[nums[i]]++;
for (int i = 0; i < n - 1; ++i) {
printf("%lld%c", pre += n - 2 * i - rite[nums[i]] + left[nums[i]], i == n - 2 ? '\n' : ' ');
rite[nums[i]]--;
left[nums[i]]++;
}
}
int main() {
int n, i = 0;
for (scanf("%d", &n); i < n; ++i)
scanf("%d", nums + i);
solve(n);
}
C++ 解法, 执行用时: 60ms, 内存消耗: 10012KB, 提交时间: 2020-10-31
#include <cstdio>
#include <unordered_map>
using namespace std;
int nums[100005];
void solve(int n) {
long long pre = 0;
unordered_map<int, int> left, rite;
for (int i = n - 1; i >= 0; --i)
rite[nums[i]]++;
for (int i = 0; i < n - 1; ++i) {
printf("%lld%c", pre += n - 2 * i - rite[nums[i]] + left[nums[i]], i == n - 2 ? '\n' : ' ');
rite[nums[i]]--;
left[nums[i]]++;
}
}
int main() {
int n, i = 0;
for (scanf("%d", &n); i < n; ++i)
scanf("%d", nums + i);
solve(n);
}