首页 > 试题广场 >

链式边权

[编程题]链式边权
  • 热度指数:910 时间限制: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)
一直不知道为什么只通过了8个用例,反复检查算法也没毛病。
最后猜测是不是int范围不够,没想到还真是这样,换成long就行了...
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] weightsStr = br.readLine().split(" ");
        int n = Integer.parseInt(str);
        int[] weights = new int[n];
        
        long[][] arr = new long[n + 1][3];
        
        HashMap<Integer, Integer> map1 = new HashMap<>();
        HashMap<Integer, Integer> map2 = new HashMap<>();
        for(int i = 0; i < n; ++i){
            weights[i] = Integer.parseInt(weightsStr[i]);
            Integer count = map1.get(weights[i]);
            if(count == null){
                count = 0;
            }
            arr[i][1] = i - count;
            map1.put(weights[i], count + 1);
        }
        map2.put(weights[n - 1], 1);
        arr[n - 1][2] = arr[n - 1][1];
        
        for(int j = n - 2; j > 0; --j){
            Integer count = map2.get(weights[j]);
            if(count == null){
                count = 0;
            }
            arr[j][2] = arr[j + 1][2] - (n - j - 1 - count) + arr[j][1];
            map2.put(weights[j], count + 1);
            
        }
        StringBuilder sb = new StringBuilder();
        for(int k = 1; k < n; ++k){
            sb.append(arr[k][2] + " ");
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.print(sb.toString());
    }
    
    
}


发表于 2022-08-31 16:25:08 回复(0)
import java.util.*;
//动态规划的思路,每新增加一个点,在原有点数对的基础上减去因为这个新增加的点损失的点数,加上新增加的点,
//用两个map,l表示当前点左侧每个点的数目,r表示当前点右侧每个点的数目
public class Main{
    public static void main(String[]args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        long[] w = new long[n];
        HashMap<Integer,Integer> l = new HashMap<>();
        HashMap<Integer,Integer> r = new HashMap<>();
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
            if(r.containsKey(arr[i])){
                r.put(arr[i],r.get(arr[i])+1);
            }else{
                r.put(arr[i],1);
            }
            l.put(arr[i],0);
        }
        w[0] = 0;
        for(int i = 0; i <n-1; i++){
            r.put(arr[i],r.get(arr[i])-1);
            //左侧i+1个点,右侧n-1-i个点
            //当左侧增加一个点arr[i]时,减去损失的点数 即 当前点arr[i]左侧所有点中与当前点不同的点数
            //l.get(arr[i])是arr[i]左侧点中arr[i]的点数,arr[i]左侧共有i个点
            //当左侧增加一个点arr[i]时,还需要加上新增加的点数, 即当前点arr[i]右侧与arr[i]不同的点数
            //r.get(arr[i])是arr[i]右侧点中arr[i]的数目,arr[i]右侧共有n-i-i个点
            long t = w[i] - (i-l.get(arr[i])) + (n-1-i-r.get(arr[i]));
            w[i+1] = t;
            System.out.print(t+" ");
            l.put(arr[i],l.get(arr[i])+1);
        }

    }
}

发表于 2020-07-17 22:32:35 回复(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)