首页 > 代码库 > [Offer收割]编程练习赛12 题目2 : 一面砖墙
[Offer收割]编程练习赛12 题目2 : 一面砖墙
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的学校的教学楼前有一面砖墙。这面墙由N层砖砌成,其中从上到下第i层包含Ci块高度相同但宽度不同的砖。
例如下图所示的这面墙,由3层砖砌成。其中第1层包含3块砖,从左到右宽度依次是6、4和3;第2层包含4块砖,从左到右依次宽度依次是4、4、2和3;第3层包含3块砖,从左到右宽度依次是5、6和2。
+------------+ | 6 | 4 |3 | +------------+ | 4 | 4 |2|3 | +------------+ | 5 | 6 |2| +------------+ ^
现在小Hi想在墙上画一道竖线,并且希望竖线穿过的砖块数目越少越好(如果竖线刚好在左右两块砖的交界处,则不会穿过砖块)。例如上例在墙^标示的位置画线,只会穿过一块砖。
注意小Hi不能在墙的左右边沿画线。
输入
第一行一个整数N,表示层数。 (1 < N <= 100000)
以下N行每行包含若干个整数。其中第一个整数Ci代表该层砖块的数目,之后Ci个整数表示从左到右每块砖的宽度。
整面墙总砖块数目不超过100000,总宽度不超过100000000。
输出
最少穿过的砖块数目。
- 样例输入
-
3 3 6 4 3 4 4 4 2 3 3 5 6 2
- 样例输出
-
1
思路
统计各层各砖块横坐标出现的次数,出现次数最多的横坐标x即画线位置,再用层数减去x的次数即可
代码
1 import java.util.HashMap; 2 import java.util.Scanner; 3 4 public class Main { 5 6 public static void main(String[] args) { 7 Scanner sc = new Scanner(System.in); 8 int n = sc.nextInt(); 9 HashMap<Integer, Integer> count = new HashMap<>(); 10 int max = 0; 11 for (int i = 0; i < n; i++) { 12 int m = sc.nextInt(); 13 for (int j = 0, x = 0; j < m; j++) { 14 x += sc.nextInt(); 15 if (j != m - 1) { 16 if (!count.containsKey(x)) { 17 count.put(x, 1); 18 } else { 19 count.put(x, count.get(x) + 1); 20 } 21 max = Math.max(max, count.get(x)); 22 } 23 } 24 } 25 System.out.println(n - max); 26 } 27 }
[Offer收割]编程练习赛12 题目2 : 一面砖墙
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。