【教3妹学编程-算法题】购买物品的最大开销

3妹：2哥，听说你今天发工资啦？ 请我吃饭怎么样，嘿嘿
2哥 : 切，你上周还发工资了呢，也没见你请我吃饭。
3妹：哎呀， 我的工资都用来双11 shopping了， 双11过后我都吃了1周土了， 好2哥，就请我吃顿肉吧。
2哥 : 3妹，花钱要有节制啊，双11虽然有一点优惠，但也不能无节制的购物啊。
3妹：衣服、包包、零食，一看到都很便宜，就没忍住，嘿嘿
2哥：你这开销也太大了！看你可怜的份上，就请你吃顿肉吧。 下个月发工资记得请回来哈。
3妹：好滴好滴，2哥最好了。
2哥 : 但是有个条件，说到最大开销，吃饭前我们要做一个关于最大开销的题目，做出来我才请客。
3妹：没问题，有吃的就有动力！

题目：

给你一个下标从 0 开始大小为 m * n 的整数矩阵 values ，表示 m 个不同商店里 m * n 件不同的物品。每个商店有 n 件物品，第 i 个商店的第 j 件物品的价值为 values[i][j] 。除此以外，第 i 个商店的物品已经按照价值非递增排好序了，也就是说对于所有 0 <= j < n - 1 都有 values[i][j] >= values[i][j + 1] 。

每一天，你可以在一个商店里购买一件物品。具体来说，在第 d 天，你可以：

选择商店 i 。
购买数组中最右边的物品 j ，开销为 values[i][j] * d 。换句话说，选择该商店中还没购买过的物品中最大的下标 j ，并且花费 values[i][j] * d 去购买。
注意，所有物品都视为不同的物品。比方说如果你已经从商店 1 购买了物品 0 ，你还可以在别的商店里购买其他商店的物品 0 。

请你返回购买所有 m * n 件物品需要的 最大开销 。

示例 1：

输入：values = [[8,5,2],[6,4,1],[9,7,3]]
输出：285
解释：第一天，从商店 1 购买物品 2 ，开销为 values[1][2] * 1 = 1 。
第二天，从商店 0 购买物品 2 ，开销为 values[0][2] * 2 = 4 。
第三天，从商店 2 购买物品 2 ，开销为 values[2][2] * 3 = 9 。
第四天，从商店 1 购买物品 1 ，开销为 values[1][1] * 4 = 16 。
第五天，从商店 0 购买物品 1 ，开销为 values[0][1] * 5 = 25 。
第六天，从商店 1 购买物品 0 ，开销为 values[1][0] * 6 = 36 。
第七天，从商店 2 购买物品 1 ，开销为 values[2][1] * 7 = 49 。
第八天，从商店 0 购买物品 0 ，开销为 values[0][0] * 8 = 64 。
第九天，从商店 2 购买物品 0 ，开销为 values[2][0] * 9 = 81 。
所以总开销为 285 。
285 是购买所有 m * n 件物品的最大总开销。
示例 2：

输入：values = [[10,8,6,4,2],[9,7,5,3,2]]
输出：386
解释：第一天，从商店 0 购买物品 4 ，开销为 values[0][4] * 1 = 2 。
第二天，从商店 1 购买物品 4 ，开销为 values[1][4] * 2 = 4 。
第三天，从商店 1 购买物品 3 ，开销为 values[1][3] * 3 = 9 。
第四天，从商店 0 购买物品 3 ，开销为 values[0][3] * 4 = 16 。
第五天，从商店 1 购买物品 2 ，开销为 values[1][2] * 5 = 25 。
第六天，从商店 0 购买物品 2 ，开销为 values[0][2] * 6 = 36 。
第七天，从商店 1 购买物品 1 ，开销为 values[1][1] * 7 = 49 。
第八天，从商店 0 购买物品 1 ，开销为 values[0][1] * 8 = 64 。
第九天，从商店 1 购买物品 0 ，开销为 values[1][0] * 9 = 81 。
第十天，从商店 0 购买物品 0 ，开销为 values[0][0] * 10 = 100 。
所以总开销为 386 。
386 是购买所有 m * n 件物品的最大总开销。

提示：

1 <= m == values.length <= 10
1 <= n == values[i].length <= 10^4
1 <= values[i][j] <= 10^6
values[i] 按照非递增顺序排序。

思路：

排序，
把所有数合并在一起排序， 详见代码

java代码：

class Solution {
    public long maxSpending(int[][] values) {
        int m = values.length, n = values[0].length;
        int[] a = new int[m * n];
        int i = 0;
        for (int[] row : values) {
            System.arraycopy(row, 0, a, i, n);
            i += n;
        }
        Arrays.sort(a);
        long ans = 0;
        for (i = 0; i < a.length; i++) {
            ans += (long) a[i] * (i + 1);
        }
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18