首页 > 试题广场 >

链式边权

[编程题]链式边权

n个点连成一条链，从左往右依次从1到n编号。相邻点之间有边相连，一共有n-1条边。所有的边从1到n-1编号，第i条边连接了点i和i+1。

第i个点有点权a_i，定义第i条边的权重为w_i：有多少点对x，y满足在第i条边的左侧（x≤i），y在第i条边的右侧（y>i），且x和y的点权不同。

给出每个点的点权，请求出所有边的边权。

第一行输入一个数n。(2≤n≤100000)
第二行输入n个数，a₁,a₂,…,a_n(1≤a_i≤10⁹)

输出n-1个数，依次为每条边的权重，不要在行末输出多余的空格。

示例1

输入

3
1 2 1

1 1

算法知识视频讲解

bandiaoz

发表于 2024-12-27 01:57:24

解题思路这道题的关键点在于：个点形成一条链，边的编号从到对于第条边，其权值定义为：在第条边左侧且点权为的点数，与在第条边右侧且点权为的点数的乘积之和需要计算每条边的权值解题思路：使用两个哈希表分别记录左侧和右侧的点权计数初始时所有点都在右侧展开全文

丨阿伟丨

发表于 2025-09-18 14:33:47

题目链接链式边权题目描述 n 个点连成一条链，编号从 1 到 n。第 i 条边连接点 i 和 i+1。每个点 i 有一个点权 a[i]。第 i 条边的权重 w[i] 定义为：满足 x <= i 且 y > i，并且 a[x] != a[y] 的点对 (x, y) 的数量。给定所展开全文

C++工程师数组分治度小满 2019 查找数学 Java工程师

来自：度小满2019秋招研发岗试卷

上传者：小小

难度：

5条回答 17收藏 9464浏览

查看代码

链式边权

扫一扫，把题目装进口袋