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(){ 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; mp[l-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; }
|