链式边权

[编程题]链式边权

热度指数：958 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

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

算法知识视频讲解

C/C++

nbgao

#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)

ElonB

"""
计算题，动态规划优化时间复杂度
"""
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)

牛客655590920号

一直不知道为什么只通过了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)

0.068

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)

牛客134603733号

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)