赞
踩
工程师小王想要从海量的网络数据中,筛选出忙时数据。由于是海量数据,小王没办法对海量数据进行排序,再取topN的忙时数据(将数据从大到小排序,取前N个)。聪明的小王想到了使用固定大小的优先级队列来进行数据筛选。为了场景简化,我们用正整数集来表示海量的网络数据,同时只取N个忙时數据,也即只取N个最大的正整数。针对每一批数据输入,单独输出一行结果,直接将N个正整数拼接完完整的一行宇符串输出即可。
输入:
第一行是正整数N和M,N为忙时个数,取值范围(1,24],M为输入的数据行数,范围[1,1000];
接下来M行,每行两个正整数A,B,以空格分隔,表示有A个重复的正整数B,A、B的取值范围[1,2147483647,如:
3 5
1 5
6 3
2 2
5 4
1 6
输出:
输出每增加一批数据对应的队列结果,直接将队列里的所有数据集从大到小拼接成字符串输出。
如上例输入的输出为:
第一次输入1个5,则队列输出为5
第二次输入6个3,则队列输出为533
第三次输入2个2,则队列输出为533
第四次输入5个4,则队列输出为544
第五次输入1个6,则队列输出为654 所以最终的输出结果为:
5
533
533
544
654
样例1:
输入:
1 3
2 3
1 6
7 4
输出:
3
6
6
解释:
只保留一个忙时
第一次输入2个3,则队列输出为3
第二次输入1个6,则队列输出为6
第三次输入7个4,则队列输出为6
所以最终输出结果为
3
6
6
样例2
输入:
24 3
10 5
5 1
20 8
输出:
5555555555
555555555511111
888888888888888888885555
解释:保留24个忙时数据
第一次输入10个5,则队列输出为5555555555
第二次输入5个1,则队列输出为555555555511111
第三次输入20个8,则队列输出为888888888888888888885555
思路:
1.每次插入number个value,然后再截取前N个元素
2.插入的时候,要寻找插入位置,那就遍历数组,若当前value大于当前位置的元素,就返回当前位置的index。然后在这个位置插入number个value
N,M = [int(i) for i in input().split()] def find_index(arr, v): index = -1 for i in range(len(arr)): if v > arr[i]: index = i break return index ret = [] array = [] for i in range(M): number, value = [int(i) for i in input().split()] if len(array) == 0: for j in range(number): array.append(value) else: index = find_index(array,value) if index != -1: for j in range(number): array.insert(index,value) else: for j in range(number): array.append(value) array = array[:N] ret.append("".join([str(i) for i in array])) for i in ret: print(i) # print(find_index([5, 3, 3],4))
公司购买一块 m x n 大小的地皮,用于建设新园区。现要将这块地皮规划为多个正方形区域,出于成本考虑,规划的正方形区域的个数越少越好,即所有区域都应纳入规划,请你帮助计算一下,最少能规划多少区域?
输入:
第一行,仅包含一个整数,代表m。
第二行,仅包含一个整数,代表n。
其中1<=n <=13,1<=m<=13
输出:
一行,仅包含一个整数,表示最少能规划块区域的数量。
样例1:
输入:
3
2
输出:3
解释:
最少能规划3个区域。
先规划1个 2x2
剩下区域规划2个 1x 1
样例2:
输入:
13
11
输出:
6
解释:最少能规划块6个区域。
先规划1个 7x7和1个6×6
再规划2个 4x4和1个5x5
最后剩下1个1x1
某公司计划在A地区选择一片区域投资建设太阳能发电站。
由于太阳能发电与地形、光服等自然条件强相关,因此在建设前,需要先进行建站进址、确定安裝太阳能板的数量,让发电利润报大。
发电站每年的利润可以用以下公式计算:
整个A地区是一个矩形区域。
前期技术人员,按照一块太阳能板覆盖的面积,将A地区内部划分为 m ×n 个地块。提前勘测并计算出每一个地块的年发电收入,使用 m× n 的发电收入矩阵表示。
为了减少管理成本,充分利用土地,必须选择一个矩形区域进行排列安装。
请实现功能,求出发电站应安装多少块太阳能板,年利润最大,最大为多少?
输入:
第一行包含两个正整数:m、n,空格分隔。表示A地区分成的m xn 个地块;0<m、n<1024。
后续n 行,每行 m 个正整数,空格分隔。表示每个小块区域的太阳能板年发电收入。0 <= 收入<100。
输出:
两个整数值,空格分隔。第一个值表示安装的太阳能板总量,第二个值表示最大利润。
注意:
1.如果存在最大利润相同的情况,则输出太阳能板总量较小的结果。
2.如果所有地块利润都是负数,则需选择损失最少的那个地块,安装一块太阳能板。
样例1:
输入:
3 2
4 10 7
3 2 9
输出:4 8
解释:
4 10 7
3 2 9
选择的是:10、7、2、9 这一正方形区域的 4 个地块。利润是:
(10+7+2+9) - (4 *5) = 8
样例2:
输入:
2 2
1 2
3 4
输出:
1 -1
解释:每个地块的利润都是负数,则选择损失最小的一块。
选择的是:10、7、2、9这一正方形区域的 4 个地块。利润是:
(10+7 +2+9)- 14*5)=8。
public static void main(String[] args) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(), m = scan.nextInt(); int[][] matrix = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { matrix[i][j] = scan.nextInt() - 5; } } int[][] prefix = new int[m][n]; for (int c = 0; c < n; c++) { prefix[0][c] = matrix[0][c]; for (int r = 1; r < m; r++) prefix[r][c] = prefix[r - 1][c] + matrix[r][c]; } int max = Integer.MIN_VALUE; int[] ans = new int[4]; for (int r1 = 0; r1 < m; r1++) for (int r2 = r1; r2 < m; r2++) for (int c2 = 0, c1 = 0, cur = 0; c2 < n; c2++) { int incr = prefix[r2][c2] - (r1 > 0 ? prefix[r1 - 1][c2] : 0); if (cur > 0) { cur += incr; } else { c1 = c2; cur = incr; } if (cur > max) { ans = new int[]{r1, c1, r2, c2}; max = cur; } } System.out.println(((ans[2] - ans[0] + 1) * (ans[3] - ans[1] + 1)) + " " + max); }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。