【[Offer收割]编程练习赛12 B】一面砖墙

【题目链接】:http://hihocoder.com/problemset/problem/1494

【题意】

【题解】



显然只要记住每一行的各个砖头的间隔处的坐标有多少个就好了；

->也就对应了从这个地方画一条竖线上去,能少碰到多少个砖头;

取少碰到的砖头数的最大值;

然后用N减去它就好；

直接用map搞



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define ps push_back

#define fi first

#define se second

#define rei(x) scanf("%d",&x)

#define rel(x) scanf("%lld",&x)

#define ref(x) scanf("%lf",&x)

typedef pair<int, int> pii;

typedef pair<LL, LL> pll;

const int dx[9] = { 0,1,-1,0,0,-1,-1,1,1 };

const int dy[9] = { 0,0,0,-1,1,-1,1,-1,1 };

const double pi = acos(-1.0);

const int N = 110;

int n;

map <int, int> dic;

vector<int> v;

int main()

{

    //freopen("F:\\rush.txt", "r", stdin);

    rei(n);

    rep1(i, 1, n)

    {

        int num = 0,tot=0;

        rei(num);

        rep1(j, 1, num)

        {

            int x;

            rei(x);

            tot += x;

            if (j == num)

                continue;

            if (!dic[tot])

            {

                v.ps(tot);

            }

            dic[tot]++;

        }

    }

    int ma = 0;

    int len = v.size();

    rep1(i, 0, len - 1)

    {

        ma = max(ma, dic[v[i]]);

    }

    printf("%d\n", n - ma);

    //printf("\n%.2lf sec \n", (double)clock() / CLOCKS_PER_SEC);

    return 0;

}