C. C. Blog

Security Research, Algorithm and Data Structure

51Nod 2495 小明垒墙

Problem

小明家要盖新房子了,但是小明家里没有钱,垒墙用的砖块都是别人用省下来的,所以砖块的长度是不固定的,但是无论怎么说,墙是垒好了,有一天小明看着墙发呆,想出来这样一个问题,问题如下:

你的面前有一堵方形的、由多行砖块组成的砖墙。 这些砖块高度相同但是宽度不同。你现在要画一条自顶向下的、穿过最少砖块的垂线。

砖墙由行的列表表示。 每一行都是一个代表从左至右每块砖的宽度的整数列表。

Solution

读入,把空的地方map标记+1,最后遍历map找其中最大值即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include<stdio.h>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<map>
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
#define db double
#define ll long long
map<int,int>mp;
int n,t,x,sum=0,ans;
inline int rd(){
int x=0;
char ch=0;
while(ch<'0'||ch>'9') {ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x;
}
int main(){
//io_opt;
n=rd();
ans=n;
for(int i=1;i<=n;i++){
t=rd();
int las=0,cur=0;
for(int j=1;j<=t;j++){
x=rd();
cur+=x;
int l=(las+1)*2,r=(las+1+x)*2;
//cout<<l<<' '<<r<<endl;
mp[l-1]++;
//mp[r-1]++;
las=las+x;
}
sum=max(sum,cur);
}
for(auto t=mp.begin();t!=mp.end();t++){
if(t->first==1||t->first==sum*2-1) continue;
ans=min(ans,n-(t->second));
}
printf("%d\n",ans);
return 0;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/61971/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!