hihoCoder 1494-一面砖墙
#1494 : 一面砖墙
时间限制: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
一面墙，由若干层砖砌成，每层有不同块不同宽度的砖。现在墙上画一道线，问最少能穿过多少块砖。重点是，如果线是画在某两块砖的交界处，则不算穿过这两块砖。 根据重点，画的线必须穿过越多层砖的交界处越好，如果这条线在这一层处于交界处，则在这一层没有和砖相交。所以我们只需统计一下所有层每两块砖之间的交界处坐标，我们在出现最多次数的交界处画一条线，则穿过最少的砖，穿过的砖块数是总的层数减去该交界坐标的频数。 代码如下： [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> using namespace std; int main() { //freopen("input.txt", "r", stdin); unordered_map<int, int> hash; int n, ci, width, total; scanf("%d", &n); total = n; while (n–) { scanf("%d", &ci); int sum = 0; while (ci–) { scanf("%d", &width); sum += width; if (ci != 0)++hash[sum]; } } int maxlevel = 0; for (auto it = hash.begin(); it != hash.end(); ++it) { maxlevel = max(maxlevel, it->second); } printf("%d\n", total – maxlevel); return 0; } [/cpp] 本代码提交AC，用时60MS。]]>
Pingback: LeetCode Brick Wall | bitJoy > code