【题目链接】:http://codeforces.com/contest/731/problem/D

【题意】



给你n个象形文;

每个象形文由l[i]个数字组成;

你可以把所有的组成象形文的数字同时增加1;

超过c的变成1;

然后让你用这个操作使得n个象形文按照字典序升序

排;

问你最小的操作次数;

【题解】



首先;

得先让这n个字符串,相邻的两个的字符串都符合字典序

即s[i]<=s[i+1];

所以;

可以分别处理出使得这n-1个相邻的关系成立的操作步数;

只考虑第一个不同的位置就好;

因为前面不管怎么改变都是一样的；

比如n-1个相邻关系种的

s[3]和s[4]

如果

s[3][i]和s[4][i]是第一个不同的位置;

②

则如果s[3][i]< s[4][i]

那么0..c-s4[i]和c-s[3][i]+1..c这个两个区间内的数对应的操作次数;

都能使s[3][i]< s[4][i]成立;

②

如果s[3][i]>s[4][i]

则c-s[3][i]+1..c-s[4][i]这个区间范围内的数对应的操作次数,都能使得s[3][i]< s[4][i]成立;

求这n-1个区间的交就好;

如果有一个区间能够使得这n-1个关系都满足则输出最小的就好;



【Number Of WA】



0



【完整代码】

#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 pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof 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 = 5e5+100;

const int M = 1e6+100;

int n,c,l[N],sum[M],sum1[M];

vector <int> G[N];

int main()

{

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

    ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use

    //init??????

    cin >> n >> c;

    rep1(i,1,n)

    {

        cin >> l[i];

        int x;

        rep1(j,1,l[i])

        {

            cin >> x;

            G[i].pb(x);

        }

    }

    rep1(i,1,n-1)

    {

        int len = min(l[i],l[i+1]);

        int j;

        for ( j = 0;j <= len-1;j++)

            if (G[i][j]!=G[i+1][j])

                break;

        if (j==len)

        {

            if (l[i]>l[i+1])

                return cout <<-1<<endl,0;

            sum[0]++;

            continue;

        }

        if (G[i][j]<G[i+1][j])

        {

            sum[0]++;

            //s[i][j]<s[i+1][j]

            sum[c-G[i+1][j]+1]--;

            sum[c-G[i][j]+1]++;

        }

        else

        {

            //s[i][j]>s[i+1][j]

            sum[c-G[i][j]+1]++;

            sum[c-G[i+1][j]+1]--;

        }

    }

    rep1(i,1,c) sum[i] += sum[i-1];

    rep1(i,0,c)

        if (sum[i]==n-1)

        {

            cout <<i<<endl;

            return 0;

        }

    cout <<-1<<endl;

    return 0;

}