海口哪里做网站,自己的网站如何优化,包装设计与制作,一般网站栏目结构3妹#xff1a;2哥#xff0c;听说你今天发工资啦#xff1f; 请我吃饭怎么样#xff0c;嘿嘿 2哥 : 切#xff0c;你上周还发工资了呢#xff0c;也没见你请我吃饭。 3妹#xff1a;哎呀#xff0c; 我的工资都用来双11 shopping了#xff0c; 双11过后我都吃了1周土…
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;}
}
