计算数组的小和_

圣诞节的安徒生

您的代码已保存
运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。

case通过率为50.00%

N = eval(input())
ls = list(map(int, input().split()))
L_sum = 0
for i in range(1,N):
    flag = ls[i]
    for j in range(i):
        if ls[j] <= flag:
            L_sum += ls[j]
print(L_sum)

版本一超时，时间复杂度超了！继续完善！

版本二：归并排序中添加一些代码（可ac）

def mergeSort(arr, left, right):
    if left == right:
        return 0
    mid = (left + right) // 2  # //是整除的意思
    return mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right) + merge(arr, left, mid, right)

def merge(arr, left, mid, right):
    res = []
    small_sub = 0
    i, j = left, mid + 1
    while i <= mid and j <= right:
        if arr[i] <= arr[j]:
            small_sub += arr[i] * (right-j+1)
            res.append(arr[i])
            i += 1
        else:
            res.append(arr[j])
            j += 1
    res += arr[i:mid + 1]
    res += arr[j:right + 1]
    arr[left:right + 1] = res
    return small_sub

N = eval(input())
ls = list(map(int, input().split()))
print(mergeSort(ls,0,N-1))

编辑于 2019-08-13 15:19:51 回复(0)

好想要offer的菜鸡

补充一个Java题解


import java.util.Scanner;

public class Main {
    private static long merge_sort(int[] nums,int[] tmp, int l, int r) {
        if (l >= r) return 0;
        int mid = l + (r - l) / 2;
        long res = merge_sort(nums, tmp, l, mid) + merge_sort(nums,tmp,mid + 1, r);

        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r) {
            if(nums[i] <= nums[j]) {
                res += (r - j + 1) * nums[i];
                tmp[k++] = nums[i++];

            } else {
                // nums[i] > nums[j]
                tmp[k++] = nums[j++];
                // 当前左边的元素都大于nums[j]
                //[l, mid] [mid + 1,  r]

            }
        }

        while (i <= mid) tmp[k++] = nums[i++];
        while (j <= r) tmp[k++] = nums[j++];

        for (int i1 = l, j1 = 0; i1 <= r ; i1++, j1++) {
            nums[i1] = tmp[j1];
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        int[] tmp = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
        }
        long sum = merge_sort(arr,tmp,0, n - 1);
        System.out.println(sum);
    }
}

编辑于 2021-03-03 17:42:19 回复(0)

Java

Castile

看了一下没有java版本的，注意两个细节，这个题目的小和，当左边的数字和当前的数相等时，也算一个小和。所有循环里面的判断if 应该是 <= 。然后就是help数组，的大小应为high-low+1，注意拷贝回原数组的细节：

import java.util.Scanner;

/**
 *
 * @author Hongliang Zhu
 * @create 2020-02-29 22:53
 */
public class Main {
    // 暴力方法 O(N^2)
    public static long  smallSum(int[] arr){
        long sum = 0;
        for(int i = 0; i < arr.length; i++){
            for(int j = 0; j < i; j++){
                if(arr[j] < arr[i]){
                    sum+=arr[j];
                }
            }
        }
        return sum;
    }

    public static long samllSum_merge(int[] arr, int low, int high){
        if(low == high) return 0;
        // 计算mid的位置
        int mid = low + (( high - low ) >> 1); // 这样可以避免溢出，而且使用了位运算，效率更高
        return samllSum_merge(arr, low, mid) + samllSum_merge(arr, mid+1, high) + merge(arr, low, mid, high);
    }
    // 归并两个有序的数组
    public static long merge(int[]arr, int low, int mid, int high){
        int[] help = new int[high - low + 1];
        long result = 0;
        int p = low;
        int q = mid + 1;
        int k = 0;
        while (p <= mid && q <= high){
            if(arr[p] <= arr[q]){ //  左边比又变小，产生小和
                result += arr[p] * ( high - q + 1);
                help[k++] = arr[p++];
            }else if(arr[p] > arr[q]){
                help[k++] = arr[q++];
            }
        }
        while(p <= mid){
            help[k] = arr[p++];
            k++;
        }
        while(q <= high){
            help[k] = arr[q++];
            k++;
        }
        // copy
        for(int i = 0; i < high - low + 1; i++){
            arr[low + i] = help[i];
        }
        return result;
    }


    public static void main(String[] args) {

        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i <n; i++){
            arr[i] = scanner.nextInt();
        }
        long sum =  samllSum_merge(arr,0, arr.length -1);

        System.out.println(sum);

    }

}

发表于 2020-03-01 12:27:02 回复(3)

C

helloxuanbao

// 结果过大会导致整型溢出，注意要用long long类型
#include <stdio.h>
#include <stdlib.h>

long long minSum(int *arr, int l, int r);

long long merge(int *arr, int l, int m, int r);

int main(void) {
    int *arr, n;
    scanf("%d", &n);
    arr = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    printf("%ld\n", minSum(arr, 0, n - 1));
    return 0; 
}

long long minSum(int *arr, int l, int r) {
    if (l == r)
        return 0;
    int m = (l + r) / 2;
    return minSum(arr, l, m) 
        + minSum(arr, m + 1, r) 
        + merge(arr, l, m, r);
}

long long merge(int *arr, int l, int m, int r) {
    int n = r - l + 1;
    int *help = (int *) malloc(n * sizeof(int));
    int index = 0;
    
    int p1 = l, p2 = m + 1;
    long long sum = 0;
    while (p1 <= m && p2 <= r) {
        if (arr[p1] <= arr[p2]) {
            sum += (r - p2 + 1) * arr[p1];
            help[index++] = arr[p1++];
        } else {
            help[index++] = arr[p2++];
        }
    }
    while (p1 <= m) {
        help[index++] = arr[p1++];
    }
    while (p2 <= r) {
        help[index++] = arr[p2++];
    }
    for (int i = 0; i < n; i++) {
        arr[l + i] = help[i];
    }
    return sum;
}

发表于 2022-04-02 21:34:35 回复(0)

C++

Dave_lzw

#include <bits/stdc++.h>
using namespace std;
const int M = 206;
int t[M];
int lowbit(int x) {
    return x & (-x);
}
void update(int x, int val) {
    while(x < M) {
        t[x] += val;
        x += lowbit(x);
    }
}
int get_sum(int x) {
    int ans = 0;
    while(x > 0) {
        ans += t[x];
        x -= lowbit(x);
    }
    return ans;
}
int main() {
    int N, x;
    cin >> N;
    long long res = 0;
    for(int i = 0; i < N; ++i) {
        cin >> x;
        x += 101;
       // cout << x << endl;
        res += get_sum(x);
        update(x, x-101);
    }
    cout << res << endl;
   
    return 0;
}

发表于 2021-12-13 10:18:54 回复(0)

Python

牛客583725131号

# python3 solution
def min_sum(array, l, r):
	if l + 1 == r:
		return 0

	l_min_sum = min_sum(array, l, (l + r) >> 1)
	r_min_sum = min_sum(array, (l + r) >> 1, r)
	extra = merge(array, l, r)
	
	return l_min_sum + r_min_sum + extra


def merge(array, l, r):
	"""Merge sort."""
	res = 0
	# sorted array[l: r]
	temp = [0 for _ in range(r - l)]
	m = (l + r) >> 1
	i, j = l, m
	k = 0
	while i < m and j < r:
		if array[i] <= array[j]:
			res += array[i] * (r - j)
			temp[k] = array[i]
			i += 1
		else:
			temp[k] = array[j]
			j += 1
		k += 1

	while i < m:
		temp[k] = array[i]
		i += 1
		k += 1

	while j < r:
		temp[k] = array[j]
		j += 1
		k += 1

	array[l: r] = temp

	return res

n = int(input())
x = [int(y) for y in input().split(' ')]
print(min_sum(x, 0, n))

编辑于 2021-05-01 23:19:15 回复(0)

C/C++

nbgao

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

long Merge(int *a, int l, int r, int m){
    int c[r-l+1];
    memset(c, 0, sizeof(c));
    int i=l, j=m+1, k=0;
    long t=0;
    while(i<=m && j<=r){
        if(a[i]<=a[j])
            t += a[i]*(r-j+1);
        c[k++] = (a[i]<=a[j]?a[i++]:a[j++]);
    }
    while(i<=m)
        c[k++] = a[i++];
    while(j<=r)
        c[k++] = a[j++];
    for(j=0;j<k;j++)
        a[l++] = c[j];
    return t;
}

long MergeSort(int *a, int l, int r){
    if(l>=r)
        return 0;
    int m = (l+r)>>1;
    return MergeSort(a, l, m) + MergeSort(a, m+1, r) + Merge(a, l, r, m);
}

int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    cout<<MergeSort(a, 0, n-1)<<endl;
    return 0;
}

发表于 2020-02-15 03:25:24 回复(2)

不知名～

归并排序的应用，当归并过程中发现左边的数小于右边的数，即得到一组小和。如1 3 5 7 和 2 4 6 8，当左边遍历第一个数，有1 < 2，则1也小于2右边的所有数，即这组小和为1*4。

注意小和结果不能用int存储，会溢出。

#include<iostream>
#include<vector>
using namespace std;

long long merge(vector<int>& nums, int l, int mid, int r) {
    vector<int> tmp(r - l + 1);
    int i = l, j = mid + 1;
    long long res = 0;
    for (int k = 0; k < tmp.size(); k++) {
        if (i > mid)
            tmp[k] = nums[j++];
        else if (j > r)
            tmp[k] = nums[i++];
        else if (nums[i] > nums[j])
            tmp[k] = nums[j++];
        else {
            res += (r - j + 1)*nums[i]; //计算小和
            tmp[k] = nums[i++];
        }
    }

    for (int cnt = l; cnt <= r; cnt++) {
        nums[cnt] = tmp[cnt - l];
    }
    return res;
}

long long smallSum(vector<int>& nums, int l, int r) {
    if (l >= r)
        return 0;
    int mid = l + (r - l) / 2;
    long long left = smallSum(nums, l, mid);
    long long right = smallSum(nums, mid + 1, r);
    return left + right + merge(nums, l, mid, r);
}

int main() {
    int n; cin >> n;
    vector<int> nums(n);
    for (int i = 0; i < n; i++) cin >> nums[i];
    cout << smallSum(nums, 0, n - 1) << endl;
    return 0;
}

发表于 2019-08-02 21:06:55 回复(1)

Spectre_

#include<iostream>
#include<vector>

using namespace std;

long merge(vector<int>& arr, int left, int mid, int right)
{
    vector<int> help(right-left+1, 0);
    int i = 0;
    int p1 = left;
    int p2 = mid + 1;
    long res = 0;
    while (p1 <= mid && p2 <= right)
    {
        res += arr[p1] <= arr[p2] ? arr[p1]*(right-p2+1) : 0;
        help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }
    while (p1 <= mid) help[i++] = arr[p1++];
    while (p2 <= right) help[i++] = arr[p2++];
    for (int num : help) arr[left++] = num;
    return res;
}

long mergeSort(vector<int>& arr, int left, int right)
{
    if (left >= right) return 0;
    int mid = left + ((right - left) >> 1);
    return mergeSort(arr, left, mid) + 
            mergeSort(arr, mid+1, right) + 
            merge(arr, left, mid, right);
}

int main()
{
    int n;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i=0; i<n; i++) cin >> arr[i];
    cout << mergeSort(arr, 0, arr.size()-1);
    return 0;
}

发表于 2019-10-09 09:29:49 回复(0)

快支棱起来呀考拉

import java.util.Scanner;

public class Main {
    static long res;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i ++){
            nums[i] = in.nextInt();
        }
        mergeSort(nums, 0, n - 1);
        System.out.println(res);
    }

    private static void mergeSort(int[] nums, int left, int right){
        if(left < right){
            int mid = left + (right - left)/2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            merge(nums, left, mid, right);
        }
    }

    private static void merge(int[] nums, int left, int mid, int right){
        int[] temparr = new int[right - left + 1];
        int index = 0;
        int index1 = left;
        int index2 = mid + 1;

        while(index1 <= mid && index2 <= right){
            if(nums[index1] <= nums[index2]){
                res += (right - index2 + 1) * nums[index1];
                temparr[index ++] = nums[index1 ++];
            }else{
                temparr[index ++] = nums[index2 ++];
            }
        }

        if(index1 <= mid){
            temparr[index ++] = nums[index1 ++];
        }
        if(index2 <= right){
            temparr[index ++] = nums[index2 ++];
        }

        System.arraycopy(temparr, 0, nums, left, right - left + 1);
    }
}

归并做法，但是不知道为什么会溢出，还没de出来

编辑于 2024-04-24 16:56:26 回复(0)

tracyss

看一眼数据范围，直接哈希表

#include <iostream>
#include <unordered_map>
using namespace std;
using LL = long long;

int n, x;
unordered_map<int, int> cnt;
LL res;

int main() {
    cin >> n;
    for (int i = 0; i < n; i ++ ) {
        scanf("%d", &x);
        for (auto[k, v]: cnt) {
            if (k <= x)
                res += v * k;
        }
        cnt[x] ++ ;
    }
    cout << res << endl;
    return 0;
}

发表于 2024-03-20 22:57:20 回复(0)

Java

我去你家

我用的是树状数组，这个和逆序对一样的，先离散化后直接查询就行，我觉得这个比分治简单多了，我是看了左神的那个视频来的
import 题目.抢红包;

import javax.management.Query;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.*;
import java.util.concurrent.ConcurrentLinkedDeque;

public class Main{
static class Input{
BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
StreamTokenizer in =new StreamTokenizer(br);
public int nextInt() throws IOException{
in.nextToken();
return (int) in.nval;
}
}
public static int getBit(int x){
return x&(-x);
}
public static int getSum(int x){ //看看那个这个数之前的前缀和，也就是小和
int ans=0;
while (x>0){
ans+=bit[x];
x-=getBit(x);
}
return ans;
}
public static void setBit(int x,int sum){ //x是下标，sum是要改变的数
while (x<bit.length){
bit[x]+=sum;
x+=getBit(x);
}
}
static int[] bit = new int[100005];
public static void main(String[] args)throws IOException {
Input sc = new Input();
int n =sc.nextInt();
int[] nums = new int[n];
Set<Integer> set = new TreeSet<>();
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
nums[i]=sc.nextInt();
set.add(nums[i]);
}
int t=1;
for (Integer a:set
) {
map.put(a,t++); //离散化
}
int ans=0;
for (int i = 0; i < n; i++) {
ans+=getSum(map.get(nums[i])); //这个数前面比他小的和，我没有直接插入全部
setBit(map.get(nums[i]),nums[i]); //一个一个插入
}
System.out.println(ans);
}
}

发表于 2023-12-27 11:52:24 回复(0)

牛客238981234号

C语言,动态规划解

当N < 200 O(n^2)

当N>200 O(n)

#include <stdio.h>
#include <stdlib.h>

long dynamic[201] = {0};

long SmallerCount(int *a,int i)
{
    long plus = 0;
    for (int j = i-1; j>= 0; j --) {
        if (a[i]==a[j]) {
            plus += dynamic[a[j]+100] +a[j];
            break;
        } else if(a[i]>=a[j]){
            plus+=a[j];
        }
    }
    dynamic[a[i]+100]=plus;
    return plus;
}

int main() {
    int size;
    long total = 0;
    scanf("%d",&size);

    int *arr = malloc(sizeof(int)*size);
    for (int i =0;i<size; i++) {
        scanf("%d",arr+i);
        total +=SmallerCount(arr,i);
    }

    printf("%ld",total);
    return 0;
}

编辑于 2023-12-05 13:00:25 回复(1)

小比尔1024

#include <iostream>
#include <vector>
using namespace std;
// 返回跨左右产生的小和累加和,左侧有序、右侧有序，让左右两侧整体有序
// arr[left...mid] arr[mid+1...right]
long merge(vector<int>& arr, int left, int mid, int right) {
	int n = right - left + 1;
	vector<int> help(n, 0);
	// 统计部分
	long ans = 0;
	for (int j = mid + 1, i = left, sum = 0; j <= right; j++) {
		while (i <= mid && arr[i] <= arr[j]) {
			sum += arr[i++];
		}
		ans += sum;
	}
	// 正常merge
	int i = 0;
	int a = left;
	int b = mid + 1;
	while (a <= mid && b <= right) {
		help[i++] = arr[a] <= arr[b] ? arr[a++] : arr[b++];
	}

	while (a <= mid) {
		help[i++] = arr[a++];
	}
	while (b <= right) {
		help[i++] = arr[b++];
	}
	for (i = 0; i < n; i++) {
		arr[i + left] = help[i];
	}
	return ans;
}


// 结果比较大，用 int 会溢出的，所以返回 long 类型
// 特别注意溢出这个点，笔试常见坑
// 返回arr[left...right]范围上，小和的累加和，同时把arr[left...right]变有序
long smallSum(vector<int>& arr, int left, int right) {
	if (left == right) return 0;
	//int mid = (left + right) / 2;
	int mid = left + ((right - left) >> 1);
	return smallSum(arr, left, mid) + smallSum(arr, mid + 1, right) + merge(arr, left, mid, right);
}

int main() {
	int n;
	cin >> n;
	vector<int> arr(n, 0);
	for (int i = 0; i < n; i++) cin >> arr[i];
	cout << smallSum(arr, 0, n - 1) << endl;
	return 0;
}

发表于 2023-11-11 11:18:27 回复(0)

ambition.xx

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
void print(vector<int> &arr) {
	for(auto &e : arr) cout << e <<	" ";
	cout << endl;
}
LL merge(vector<int> &arr, int left, int mid, int right) {
//    printf("%s left = %d mid = %d right = %d \n", __func__, left, mid, right);
    vector<int> help(right - left);
    LL s = 0;
    int i = left, j = mid, k = 0;
    while(i < mid and j < right) {
        if(arr[i] <= arr[j]) {
            s += arr[i] * (right - j);
        }
        help[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
    }
    while(i < mid) {
        help[k++] = arr[i++];
    }
    while(j < right){
        help[k++] = arr[j++];
    }
//    print(help);
    copy(help.begin(), help.end(), arr.begin() + left);
    
    return s;
}
LL mergeSort(vector<int> &arr, int left, int right) {
//    printf("%s left =  %d right = %d \n", __func__ ,left, right );
    if(left + 1 >= right){
        return 0;
    }
    
    int mid = (left + right) / 2;
//    printf("mid = %d \n", mid );
    LL sum  = 0;
    sum += mergeSort(arr, left, mid);
    sum += mergeSort(arr, mid, right);
    sum += merge(arr, left, mid, right);
    return sum;
}
int main(){
	//freopen("in2.txt", "r", stdin);
    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &e : arr) cin >> e ;
//    printf("err\n");
    cout << mergeSort(arr, 0, arr.size());
    return 0;
}

发表于 2022-10-22 23:24:12 回复(0)

麦芒2021

归并排序：

每次归并时，左边半部分是排序好的，右边半部门也是归并好的，其内部大小已经加入到最终的结果，每次归并只需要考虑左边的值是否小于等于右边的值即可，如果小于等于，则最终的结果需要加上left[i]*(right-j+1)

#include "iostream"
#include "vector"
#include "algorithm"

using namespace std;

void merge(vector<int>& s,int left,int right,long long& sum)
{
    if(left>=right) return;
    if(right-1==left)
    {
        if(s[right]>=s[left]) sum+=s[left];
        else swap(s[left],s[right]);
        return;
    }
    int mid=(left+right)>>1;
    merge(s,left,mid,sum);
    merge(s,mid+1,right,sum);
    vector<int> tmp(mid-left+1);
    for(int i=0;i<tmp.size();i++)
    {
        tmp[i]=s[left+i];
    }
    int i=0,j=mid+1,k=left;
    while(i<tmp.size()&&j<=right)
    {
        if(tmp[i]<=s[j]){sum+=tmp[i]*(right-j+1);s[k]=tmp[i];i++;k++;}
        else {s[k]=s[j];j++;k++;}
    }
    while(i<tmp.size())
    {
        s[k]=tmp[i];i++;k++;
    }
    while(j<=right)
    {
        s[k]=s[j];j++;k++;
    }
    return;
}

int main()
{
    int len;
    cin>>len;
    vector<int> s(len,0);
    for(int i=0;i<len;i++)cin>>s[i];
    long long sum=0;
    if(len<=1) {cout<<sum;return 0;}
    merge(s,0,len-1,sum);
    cout<<sum;
    return 0;
}

发表于 2022-05-08 15:00:42 回复(0)

C++

木子蓝色

归并排序的应用

#include <bits/stdc++.h>

using namespace std;


long long merge(vector<int>& nums, int left, int mid, int right){
    int i = left, j = mid + 1;
    vector<int> tmp;
    long long res = 0;    // 使用 64 位 int 存储
    while(i <= mid && j <= right){
        // 相比标准的归并排序，多了这一行，进行数组小和的统计
        res += nums[i] <= nums[j] ? nums[i] * (right - j + 1): 0;
        
        if(nums[i] <= nums[j]){
            tmp.push_back(nums[i]);
            i++;
        }
        else {
            tmp.push_back(nums[j]);
            j++;
        }
        
    }
    
    while(i <= mid){
        tmp.push_back(nums[i]);
        i++;
    }
    while(j <= right){
        tmp.push_back(nums[j]);
        j++;
    }
    for(int i = 0; i < tmp.size(); ++i){
        nums[left + i] = tmp[i];
    }
    return res;
}

long long mergeSort(vector<int>& nums, int left, int right){
    if(left >= right) return 0;
    int mid = left + (right - left) / 2;
    return mergeSort(nums, left, mid)
        + mergeSort(nums, mid + 1, right)
        + merge(nums, left, mid, right);
}

int main()
{
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; ++i) cin >> nums[i];
    cout << mergeSort(nums, 0, nums.size() - 1);
    return 0;
    
}

发表于 2022-04-07 21:50:47 回复(0)

花开花开

n = int(input())
nums = list(map(int, input().split()))
ans = 0

def merge(arr, start, end):
    global ans
    start1, end1 = start, (start + end) // 2
    start2, end2 = end1 + 1, end
    temp = []
    p1, p2 = start1, start2
    while p1 <= end1 and p2 <= end2:
        if arr[p1] <= arr[p2]:
            temp.append(arr[p1])
            ans += arr[p1] * (end2 - p2 + 1)
            p1 += 1
        else:
            temp.append(arr[p2])
            p2 += 1
    while p1 <= end1:
        temp.append(arr[p1])
        p1 += 1
    while p2 <= end2:
        temp.append(arr[p2])
        p2 += 1
    for i in range(len(temp)):
        arr[start + i] = temp[i]

def mergeSort(arr, start, end):
    if start >= end: return
    mid = (start + end) // 2
    mergeSort(arr, start, mid)
    mergeSort(arr, mid + 1, end)
    merge(arr, start, end)

mergeSort(nums, 0, n - 1)
print(ans)

python代码

发表于 2022-03-30 19:29:56 回复(0)

C++

東风谷早苗

值域挺小的，哈希表秒切

#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int N=1e5+10;

unordered_map <int,ll>ma;
int n,a[N];
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(auto it:ma){
            if(it.first<=a[i]){
                ans=ans+it.second;
            }
            
        }
        ma[a[i]]+=a[i];
    }
    cout<<ans<<"\n";
}

发表于 2022-01-06 23:08:29 回复(0)

Java

pein531

左老师课堂上的经典例题，在归并排序时计算小和，时间复杂度为O(n*logn)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static long smallSum = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strNums = br.readLine().split(" ");
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) nums[i] = Integer.parseInt(strNums[i]);
        mergeSort(nums, 0, nums.length - 1);
        System.out.println(smallSum);
    }
    
    private static void mergeSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int mid = left + ((right - left) >> 1);
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        mergeCount(nums, left, mid, right);
    }
    
    private static void mergeCount(int[] nums, int left, int mid, int right) {
        int[] help = new int[right - left + 1];
        int p1 = left, p2 = mid + 1, p = 0;
        while(p1 <= mid && p2 <= right){
            smallSum += nums[p1] <= nums[p2] ? (right - p2 + 1) * nums[p1]: 0;
            help[p ++] = nums[p1] <= nums[p2]? nums[p1 ++]: nums[p2 ++];
        }
        while(p1 <= mid)
            help[p ++] = nums[p1 ++];
        while(p2 <= right)
            help[p ++] = nums[p2 ++];
        for(int i = 0; i < help.length; i++)
            nums[left + i] = help[i];
    }
}

发表于 2021-11-13 12:37:45 回复(2)

计算数组的小和

输入描述:

输出描述:

输入

输出

输入

输出

备注:

问题信息

热门推荐

通过挑战的用户

相关试题