首页 > 试题广场 > 链式边权
[编程题]链式边权
  • 热度指数:229 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解

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

i个点有点权ai,定义第i条边的权重为wi:有多少点对xy满足在第i条边的左侧(x≤i),y在第i条边的右侧(y>i),且xy的点权不同。

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


输入描述:

第一行输入一个数n。(2≤n≤100000)

第二行输入n个数,a1,a2,…,an (1≤ai≤109)



输出描述:
输出n-1个数,依次为每条边的权重,不要在行末输出多余的空格。
示例1

输入

3
1 2 1

输出

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

int main(){
    int n;
    cin>>n;
    int a[n];
    long w[n];
    map<int,int> l,r;
    for(int i=0;i<n;i++){
        cin>>a[i];
        r[a[i]]++;
        l[a[i]] = 0;
    }
    w[0] = 0;
    for(int i=0;i<n-1;i++){
        r[a[i]]--;
        long t = w[i] - (i-l[a[i]]) + (n-1-i-r[a[i]]);
        w[i+1] = t;
        l[a[i]]++;
    }
    for(int i=1;i<n;i++){
        if(i==n-1)
            cout<<w[i]<<endl;
        else
            cout<<w[i]<<" ";
    }
    return 0;
}

发表于 2019-11-20 01:39:01 回复(0)
"""
计算题,动态规划优化时间复杂度
"""
import sys
from collections import Counter

if __name__ == '__main__':
    # sys.stdin = open("input.txt", "r")
    n = int(input())
    a = list(map(int, input().strip().split()))
    right = Counter(a)
    left = Counter([])
    ans = [0]
    for t in range(n - 1):
        right[a[t]] -= 1
        tmp = (ans[-1] - (t - left[a[t]])) + (n - 1 - t - right[a[t]])
        ans.append(tmp)
        left[a[t]] += 1
    print(' '.join(map(str, ans[1:])))

编辑于 2019-10-06 21:49:46 回复(0)