首页 > 试题广场 > 链式边权
[编程题]链式边权
  • 热度指数:667 时间限制: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)
import java.util.*;
public class Main {
    public static void main(String[] str) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] a = new int[n];
            Map<Integer, Integer> r = new HashMap();
            Map<Integer, Integer> l = new HashMap();
            long[] w = new long[n];
            for (int i = 0; i < n; i++) {
                a[i] = in.nextInt();
                if (!r.containsKey(a[i])) 
                    r.put(a[i], 1);
                else
                    r.put(a[i], r.get(a[i])+1);
                l.put(a[i], 0);
            }
            w[0] = 0;
            for (int i = 0; i < n-1; i++) {
                r.put(a[i], r.get(a[i])-1);
                w[i+1] = w[i] - (i - l.get(a[i])) + (n - i - 1 - r.get(a[i]));
                l.put(a[i], l.get(a[i])+1);
            }
            for (int i = 1; i < n; i++) {
                if (i != n-1) 
                    System.out.print(w[i] + " ");
                else 
                    System.out.println(w[i]);
            }
        }
        return;
    }
}
发表于 2020-06-18 10:49:21 回复(0)