首页 > 试题广场 >

数组单调和

[编程题]数组单调和
  • 热度指数：13468 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。

给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例： 
[1,3,5,2,4,6],6
返回：27
算法知识视频讲解
添加回答
C/C++
Debug丶头像 Debug丶 
class MonoSum {
public:
    int calcMonoSum(vector<int> A, int n) {
        // write code here
        int nSum = 0;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (A[j] >= A[i])
                    nSum += A[i];
        return nSum;
    }
}; 

发表于 2019-08-27 15:31:30 回复(0)
我信仰科学头像 我信仰科学 
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        return MergeSort(A,0,n-1);
    }
    public int MergeSort(int[] arr, int startIndex, int endIndex){
        int total=0;
        if(startIndex < endIndex)
        {
            int midIndex = (startIndex + endIndex) / 2;
            total+=MergeSort(arr, startIndex, midIndex);
            total+=MergeSort(arr,midIndex+1, endIndex);
            total+=Merge(arr, startIndex, midIndex, endIndex);
        }
        return total;
    }
    public int Merge(int[] arr,int start,int mid,int end){
        int total=0;
        for(int i=mid+1;i<=end;i++){
            for(int j=start;j<=mid;j++){
                if(arr[i]>=arr[j])
                    total+=arr[j];
            }
        }
        return total;
    }
}

发表于 2017-09-20 17:24:39 回复(1)
Java
冬木_头像 冬木_ 
 public static int calcMonoSum(int[] A, int n) {
		int[] sum = new int[n];
		sum[0] = 0;
		for (int i = 1; i < n; i++) {
			if (A[i] > A[i - 1]) {
				sum[i] = sum[i - 1] + A[i - 1];
				for (int j = i - 2; j >= 0; j--) {
					if (A[j] > A[i - 1] && A[j] <= A[i]) {
						sum[i] += A[j];
					}
				}
			} else if (A[i] == A[i - 1]) {
				sum[i] = sum[i - 1] + A[i - 1];
			} else {
				int p = i - 2;
				for (; p >= 0 && A[p] > A[i]; p--){}
				if (p >= 0 && A[p] == A[i]) {
					sum[i] = sum[p] + A[p];
				} else if (p >= 0 && A[p] < A[i]) {
					sum[i] = sum[p] + A[p];
					for (int k = p - 1; k >= 0; k--) {
						if (A[k] > A[p] && A[k] <= A[i]) {
							sum[i] += A[k];
						}
					}
				}
			}
		}
		int s = 0;
		for (int i = 0; i < n; i++) {
			s += sum[i];
		}
		return s;
	}

按照DP的思想写的，计算过的一些子问题不重复计算，可是感觉不对
时间复杂度的话应该小于N方，但是自己试验了很多数据，整型并不比暴力法用时短，浮点则比暴力法用时短

编辑于 2017-03-21 10:43:40 回复(1)
Scheaven头像 Scheaven 
import java.util.*;
/*
 * @question 现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。
                                      给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。
                                      测试样例：
 * @author snow
 * @time 2016-08-06 16:50
 * @算法思想很简单不写了
 */
public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        int  sum = 0;
        for(int i=1;i<=n;i++){
            sum = sum + getSubSum(Arrays.copyOfRange(A,0,i+1),i);
        }
        return sum;
        // write code here
    }
    
    private int getSubSum(int[] B,int n){
        int sub = 0;
        for(int i:B){
            if(i<=B[n]){
                sub = sub + i;
            }
        }
        return sub - B[n];
    }
}

编辑于 2016-08-06 17:09:21 回复(1)
什么是一个响亮的名字头像 什么是一个响亮的名字
class MonoSum {
public:
    int calcMonoSum(vector<int> A, int n) {
        // write code here
    int sum = 0;
for (int i=1; i<n; ++i)
{
for (int j=0; j<i; ++j)
{
if (A[j] <= A[i])
{
sum += A[j];
}
}
}
return sum;
    }
};
发表于 2016-07-05 20:11:07 回复(0)
牛客400998号头像 牛客400998号 
解题思路：计算数组中每个元素的右边大于等于它的元素个数，有几个，就表示它被加了几次，这样只需定义一个函数，来计算元素右边大于等于它的元素个数即可。
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        int monSum=0;
        if(n==1)
            return monSum;
        for(int i=0;i<n;i++)
        {
           int count=calcCount( A,n,i);
            monSum=monSum+A[i]*count;
            
        }
        return monSum;
    }
    public int calcCount(int[] A,int n,int index)
    {
        int count=0;
    	for(int i=index+1;i<n;i++)
        {
     		 if(A[i]>=A[index])
                 count++;
        }  
        return count;
    }
}

发表于 2016-05-17 19:11:06 回复(1)
牛客703246号头像 牛客703246号 
新建了一个数组来纪录比后面小的次数
class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
        i=1
        L=[]
        for x in A[:n-1]:
            j=0
            for y in A[i:n]:
                if x<=y:
                    j+=1
            i+=1
            L.append(j)
        return sum([a[0]*a[1] for a in zip(A[:n-1],L)])

发表于 2016-05-13 21:48:37 回复(1)
C/C++
kakaan头像 kakaan
说高端点这叫动态规划的解法，
其实就是Naive搜索
从0~n-1，比较第i个数左边的数字，满足要求（小于等于）的加大fi上。
一轮下来获得一个fi，加到msum上，
所有数字扫描完就得到了结果 
    int calcMonoSum(vector<int> A, int n) {
        int msum = 0;
        for(int i=1;i<n;i++)
        {
            int fi = 0;
            for(int j=0;j<i;j++)
            	if(A[j]<=A[i])
            		fi+= A[j];
            msum += fi;
        }
		return msum;
    }

发表于 2016-08-29 23:07:19 回复(9)
ZackWang头像 ZackWang
递归，很简单的解法。 
class MonoSum {
public:
    int calcMonoSum(vector<int> A, int n) {
        // write code here
        if(n > 500) return -1;
        if(n <= 0) return 0;
        int sum = 0;
        for(int i = 0; i < n - 1; ++i)
        {
            if(A.at(i) <= A.at(n - 1))
                sum += A.at(i);
        }
        
        return sum + calcMonoSum(A, n - 1); 
    }
};

发表于 2018-03-13 23:33:20 回复(0)
牛客135210号头像 牛客135210号 
这题利用归并排序的特点：在归并阶段，比如左边{2, 5} 右边{3, 6}。左边的2肯定在3和6的前面，5也肯定在6前面，所以此次归并可以算一个单调和2 * 2 + 5 * 1=9。每次归并都计算就可得到总的和
class MonoSum {
public:
    int count = 0;
    void merge(vector<int> &arr, int start, int mid, int end) {
        vector<int> res;
        int left_index = start;
        int right_index = mid + 1;
        while(left_index <= mid && right_index <= end) {
            if(arr[left_index] <= arr[right_index]) {//合并时左边的更小
                count += (end - right_index + 1) * arr[left_index];
                
                res.push_back(arr[left_index]);
                left_index++;
            }
            else {
                res.push_back(arr[right_index]);
                right_index++;
            }
        }
        for(int i = left_index; i <= mid; i++) {
            res.push_back(arr[i]);
        }
        for(int i = right_index; i <= end; i++) {
            res.push_back(arr[i]);
        }
        for(int i = start; i <= end; i++) {
            arr[i] = res[i - start];
        }
    }
    void mergeSort(vector<int> &arr, int start, int end) {
        
        int mid = start + (end - start) / 2;
        if(mid > start) {
            mergeSort(arr, start, mid);
        }
        if(end > mid + 1) {
            mergeSort(arr, mid + 1, end);
        }
        merge(arr, start, mid, end);
    }
    int calcMonoSum(vector<int> A, int n) {
        // write code here
        if(n < 2) {
            return 0;
        }
        mergeSort(A, 0, n - 1);
        return count;
    }
};

发表于 2016-03-10 21:42:10 回复(4)
南山北头像 南山北
//虽然我不知道我这种方法是不是最优的，但是我感觉我这个思路绝对是最简单的
 public int calcMonoSum(int[] A, int n) {
        int  count = 0;
        for(int i = 1 ; i < n ;i++){
            for(int j = i-1 ; j >= 0 ; j--){
                if(A[j]<=A[i]){
                    count += A[j];
                }
            }
        }
        return count;
    }
编辑于 2016-08-12 22:11:33 回复(7)
Python
华科平凡头像 华科平凡

python一行 

def calcMonoSum(self, A, n):
        return sum(map(lambda i: sum(filter(lambda c: c <= A[i], A[:i])), range(1, n)))


编辑于 2019-10-06 21:19:18 回复(2)
C/C++
nbgao头像 nbgao 
class MonoSum {
public:     int result = 0;
    int calcMonoSum(vector<int> A, int n) {
        if(n<2)
            return 0;
        MergeSort(A, 0, n-1);
        return result;
    }
    void MergeSort(vector<int> &A, int s, int e){
        int mid = (s+e)/2;
        if(mid > s)
            MergeSort(A, s, mid);
        if(mid+1 < e)
            MergeSort(A, mid+1, e);
        Merge(A, s, mid, e);     }     void Merge(vector<int> &A, int s, int mid, int e){         vector<int> L(A.size(),0);         int i = s;         int j = mid+1;         int k = s;                  while(i<=mid && j<=e){             if(A[i] <= A[j]){                 result += (e-j+1)*A[i];                 L[k++] = A[i++];             }else                 L[k++] = A[j++];         }                  while(i <= mid)             L[k++] = A[i++];         while(j <= e)             L[k++] = A[j++];         for(int i=s;i<=e;i++)             A[i] = L[i];     }
};

发表于 2017-10-10 01:32:10 回复(0)
Python
改个名字解解毒...头像 改个名字解解毒... 
#!/usr/bin/env python
#-*- coding:utf8 -*-
# -*- coding:utf-8 -*-

class MonoSum:
    def calcMonoSum(self, A, n):
        # write code here
        nums = [0 for i in range(n)]
        for i in range(1,n):
            for j in range(i):
                if A[i] >= A[j]:
                    nums[i] += A[j]
        return sum(nums)

发表于 2017-08-08 10:32:43 回复(0)
小学作业多头像 小学作业多
利用归并排序，在对有序子数组进行merge的同时，累加数组小和，时间复杂度O(nlogn)， 
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        if (A == null || n == 0) {
            return 0;
        }
        return mergeSortRecursion(A, 0, n - 1);
    }
    
    /**
     * 递归实现归并排序
     *
     * @param arr
     * @param l
     * @param r
     * @return 返回数组小和
     */
    public static int mergeSortRecursion(int[] arr, int l, int r) {
        if (l == r) {   // 当待排序数组长度为1时，递归开始回溯，进行merge操作
            return 0;
        }
        int mid = (l + r) / 2;
        return mergeSortRecursion(arr, l, mid) + mergeSortRecursion(arr, mid + 1, r) + merge(arr, l, mid, r);
    }

    /**
     * 合并两个已排好序的数组s[left...mid]和s[mid+1...right]
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @return 返回合并过程中累加的数组小和
     */
    public static int merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];    // 辅助存储空间 O(n)
        int index = 0;
        int i = left;
        int j = mid + 1;
        int smallSum = 0;       // 新增，用来累加数组小和
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                // 当前一个数组元素小于或等于后一个数组元素时，累加小和
                // s[i] <= s[j] -> s[i] <= s[j]...s[right]
                smallSum += arr[i] * (right - j + 1);
                temp[index++] = arr[i++];
            } else {
                temp[index++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[index++] = arr[i++];
        }
        while (j <= right) {
            temp[index++] = arr[j++];
        }
        for (int k = 0; k < temp.length; k++) {
            arr[left++] = temp[k];
        }
        return smallSum;
    }
}

发表于 2017-07-28 10:42:57 回复(3)
吾生有你头像 吾生有你 
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        int count=0;
        for(int i=0; i<n; i++){
            int[] temp=new int[i];
            for(int j=0; j<i; j++)
                temp[j]=A[j];
            count+=f(A[i],temp);
        }
        return count;
    }
    public int f(int a, int[] temp){
        int count=0;
        for(int i=0; i<temp.length; i++){
            if(temp[i]<=a)
                count+=temp[i];
        }
        return count;
    }
}

发表于 2018-06-28 20:04:24 回复(0)
编程我很菜头像 编程我很菜 
给出一个用动态规划求解的方法
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        int len =A.length;
        int[] dandiao = new int[len];
        //初始化
        for(int i=0;i<len;i++){
        	dandiao[i] = 0; 
        }
        for(int i=1;i<len;i++){
            for(int j=0;j<i;j++){
                if(A[j]<=A[i]){
                	if(dandiao[i]<=dandiao[j]+A[j]){
                		dandiao[i]=dandiao[j]+A[j];
                	}else{
                		dandiao[i] = dandiao[i]+A[j];
                	}
                    
                }

            }
        }
        System.out.println(Arrays.toString(dandiao));
        int res = 0; 
        for(int i=0;i<dandiao.length;i++){
        	res = res+dandiao[i];
        }
        
        return res;
    }
}

发表于 2016-08-11 10:35:56 回复(4)
Java
脱缰的哈士奇～头像 脱缰的哈士奇～

「数组单调和」，也叫「数组小和」，指的是数组中所有元素 i 的 f(i) 值之和。这里的 f(i) 函数定义为元素 i 左边（不包括其自身）小于等于它的数字之和。

举个例子，对数组 [1,3,5,2,4,6]，其数组单调和（最小和）为 27，求解过程如下。

f(arr[0]) = 0
f(arr[1]) = 1
f(arr[2]) = 1 + 3 = 4
f(arr[3]) = 1
f(arr[4]) = 1 + 3 + 2 = 6
f(arr[5]) = 1 + 3 + 5 + 2 + 4 = 15

sum = 1 + 4 + 1 + 6 + 15 = 27

此处，以 smallSum(i) 表示数组前 i 个元素的数组单调和（最小和），观察其计算规律。

# [1]
smallSum(0) = 0;
# [1,3]
smallSum(1) = 1 = smallSum(0) + 1
# [1,3,5]
smallSum(2) = 5 = smallSum(1) + (1+3)
# [1,3,5,2]
smallSum(3) = 6 = smallSum(2) + (1)
# [1,3,5,2,4]
smallSum(4) = 12 = smallSum(3) + (1+3+2)
# [1,3,5,2,4,6]
smallSum(5) = 27 = smallSum(4) + (1+3+5+2+4)

可以发现，对数组的单调和（最小和），有如下计算公式。

smallSum(i+1) = smallSum(i) + f(arr[i+1])

f(arr[i]) 表示元素 arr[i] 左边（不包括其自身）小于等于它的数字之和

对于 f(arr[i]) 的计算，可在归并排序的 merge 阶段中计算。

举个例子，此处以数组 [1,3,5,2] 进行说明

  1. smallSum = 0，表示数组单调和（最小和）
  2. 对 [1] 和 [3] 进行 merge 时，发现左边元素 1 小于右边元素 3，故 smallSum += 1*1 = 1，即上文分析的 smallSum(1) = 1
  3. 对 [5] 和 [2] 进行 merge 时，没有发现左边元素小于右边元素，不对 smallSum 处理
  4. 对 [1,3] 和 [5,2] 进行 merge 时，发现左边元素 1 小于两个元素[5,2]，左边元素 3 小于右边 1 个元素 [5]，故 smallSum += 1*2 + 3*1 = 6，即上文分析的 smallSum(3) = 6

最后，给出使用归并排序计算数组单调和（最小和）的代码实现。

import java.util.*;

public class MonoSum {
    public int smallCount = 0;

    public int calcMonoSum(int[] A, int n) {
        mergeSort(A,n);
        return smallCount;
    }

    public void mergeSort(int[] A, int n){
        if(A == null || n <= 1){
            return;
        }
        sort(A,0,n-1);
    }

    public void sort(int[] A, int left,int right){
        if(left == right){
            return;
        }
        int mid = left + (right - left)/2;
        sort(A,left,mid);
        sort(A,mid+1,right);
        merge(A,left,mid,right);
    }

    public void merge(int[] A, int left,int mid,int right){
        int p1 = left;
        int p2 = mid+1;
        int[] tempArr = new int[right-left+1];
        int index = 0;
        while(p1 <= mid && p2 <= right){
            if(A[p1] <= A[p2]){
                //计算数组最小和
                smallCount += (right-p2+1) * A[p1]; 
                tempArr[index++] = A[p1++];
            } else {
                tempArr[index++] = A[p2++];
            }
        }
        while(p1 <= mid){
            tempArr[index++] = A[p1++];
        }
        while(p2 <= right){
            tempArr[index++] = A[p2++];
        }
        //copy data
        for(int i=0;i<tempArr.length;i++){
            A[left+i] = tempArr[i];
        }
    }
}
发表于 2022-06-15 21:03:06 回复(0)
牛客673900671号头像 牛客673900671号 
import java.util.*;

public class MonoSum {
    public int calcMonoSum(int[] A, int n) {
        // write code here
        // 思路，通过循环，将数组A分割成1~n个元素的小数组，再进行比较加和
        int sum = 0;
        for (int i=0; i<n; i++) {
            int[] child = new int[i];
            for (int j=0; j<i; j++) {
                child[j] = A[j];
            }
            // 以上可得到分割后的每个小数组child
            for(int k=0; k<child.length; k++) {
                if (child[k] <= A[i]) {
                    sum += child[k];
                }
            }
        }
        return sum;
    }
}

发表于 2023-02-14 19:46:45 回复(0)
咕咚选手头像 咕咚选手 
#include <iostream>
#include <vector>
using namespace std;

// 方法一
// 参数n为以下标n-1为参照，求其前面的单调和
// int cal(const vector<int> &nums, int n) {
//     if(n <= 1) return 0;
//     if(n > 2e5) return 0;
//     int res = 0;
//     for(int i = 0; i < n - 1; ++i) {
//         if(nums[i] <= nums[n - 1]) {
//             res += nums[i];
//             res %= (int)(1e9 + 7);
//         }
//     }
//     return res + cal(nums, n - 1);
// }
// int main()
// {
//     int n, buf;
//     cin >> n;
//     vector<int> nums;
//     for(int i = 0; i < n; ++i) {
//         cin >> buf;
//         nums.push_back(buf);
//     }
//     cout << cal(nums, n) << endl;
//     return 0;
// }


// 方法二
// int main()
// {
//     int n, buf, res = 0;
//     cin >> n;
//     vector<int> nums;
//     for(int i = 0; i < n; ++i) {
//         cin >> buf;
//         nums.push_back(buf);
//     }
//     for(int i = 1; i < n; ++i) {
//         for(int j = 0; j < i; ++j) {
//             if(nums[j] <= nums[i]) {
//                 res += nums[j];
//                 res %= (int)(1e9+7);
//             }
//         }
//     }
//     cout << res << endl;
//     return 0;
// }

// 方法三
void merge(vector<int> &nums, int start, int mid, int end, int &count) {
    vector<int> res;
    int left_index = start, right_index = mid + 1;
    while(left_index <= mid && right_index <= end) {
        if(nums[left_index] <= nums[right_index]) {
            count += (end - right_index + 1) * nums[left_index];
            count %= (int)(1e9+7);
            res.push_back(nums[left_index++]);
        } else {
            res.push_back(nums[right_index++]);
        }
    }
    for(int i = left_index; i <= mid; ++i) {
        res.push_back(nums[i]);
    }
    for(int i = right_index; i <= end; ++i) {
        res.push_back(nums[i]);
    }
    for(int i = start; i <= end; ++i) {
        nums[i] = res[i - start];
    }
}

void mergeSort(vector<int> &nums, int start, int end, int &res) {
    int mid = start + (end - start) / 2;
    if(mid > start) {
        mergeSort(nums, start, mid, res);
    }
    if(end > mid + 1) {
        mergeSort(nums, mid + 1, end, res);
    }
    merge(nums, start, mid, end, res);
}

int main()
{
    int n, buf, res = 0;
    cin >> n;
    vector<int> nums;
    for(int i = 0; i < n; ++i) {
        cin >> buf;
        nums.push_back(buf);
    }
    if(n < 2 || n > 2e5) res = 0;
    else mergeSort(nums, 0, n - 1, res);
    cout << res << endl;
    
    return 0;
}

发表于 2022-10-15 19:57:36 回复(0)
提交观点

问题信息

动态规划 查找
来自：经典算法题精讲（六）-...
难度：
119条回答 31032浏览

热门推荐

通过挑战的用户

查看代码

相关试题

数组单调和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号