n个点连成一条链,从左往右依次从1到n编号。相邻点之间有边相连,一共有n-1条边。所有的边从1到n-1编号,第i条边连接了点i和i+1。
第i个点有点权ai,定义第i条边的权重为wi:有多少点对x,y满足在第i条边的左侧(x≤i),y在第i条边的右侧(y>i),且x和y的点权不同。
给出每个点的点权,请求出所有边的边权。
n个点连成一条链,从左往右依次从1到n编号。相邻点之间有边相连,一共有n-1条边。所有的边从1到n-1编号,第i条边连接了点i和i+1。
第i个点有点权ai,定义第i条边的权重为wi:有多少点对x,y满足在第i条边的左侧(x≤i),y在第i条边的右侧(y>i),且x和y的点权不同。
给出每个点的点权,请求出所有边的边权。
第一行输入一个数n。(2≤n≤100000)
第二行输入n个数,a1,a2,…,an (1≤ai≤109)
输出n-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; }
""" 计算题,动态规划优化时间复杂度 """ 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:])))
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()); } }
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); } } }