huring
0%

51nod-2523-小b删列

Posted on In

题目：

b有一个n*m的矩阵A，矩阵的每个元素为一个字符，现在她希望删除其中的一些列，使得剩下的列在每一行形成的字符串的字典序不降。

即对于第i行，将剩下的列上的字符顺序拼接，形成一个字符串，字符串记作a[i]。要求a[i]<=a[i+1](i=1..n-1)。

请问小b最少要删多少列。

如A = {“abcdef”, “uvwxyz”}，删除的列为第1,3,4列，删除后 A 为 {“bef”, “vyz”}，且 “bef” <= “vyz”

样例解释：

删掉第一列，剩下的是”a” “b” “c”，”a” <= “b” <= “c”，满足条件。

输入

第一行输入一个正整数n，表示矩阵A的行数；
之后n行每行输入一个字符串，其长度相等；
1≤n,m≤100。

输出

输出一个非负整数，表示删掉的列数

输入样例

1
2
3
4
3
ca
bb
ac

输出样例

1
1

题解：

首先看第一列是否有降序字符，如果有，则第一列删除，否则，看时候有相同字符的行，记录这些有相同字符行的位置，再进行下一列的判断时，只判断每个相同字符的行即可。

代码：

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<set>
#include<vector>
using namespace std;
char a[110][110];
vector<int> s[26];
vector<int> tmp[26];
bool isR()
{
    for(int i = 0; i < 26; i++){
        if(s[i].size() > 1)
            return true;
    }
    return false;
}
int main()
{
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)  
        scanf("%s", a[i]);
    int m = strlen(a[0]);
    for(int i = 0; i < n; i++)
        s[0].push_back(i);
    int ans = 0;
    int p = 0;
    //printf("m %d\n",m);
   // for(int i = 0; i < n; i++)  
      //  printf("%s\n", a[i]);
   // for(int i = 0; i < 26; i++)
       // printf("%d:%d\n", i,s[i].size());
    while(isR() && p < m){
        //printf("p %d\n", p);
        bool flag = true;
        for(int i = 0; i < 26; i++){
            if(s[i].size() > 1){
                int l = s[i].size();
                for(int j = 1; j < l; j++){
                    if(a[s[i][j]][p] < a[s[i][j - 1]][p]){
                        flag = false;
                        break;
                    }
                }
            }
            if(!flag)
                break;
        }
        if(flag == false){
            ans++;
           // printf("ans : %d\n", ans);
        }
        else{
            
            for(int i = 0; i < 26; i++){
                if(s[i].size() > 1){
                    int l = s[i].size();
                  //  printf("l %d\n", l);
                    for(int j = 1; j < l; j++){
                        if(a[s[i][j]][p] == a[s[i][j - 1]][p]){
                            tmp[a[s[i][j]][p] - 'a'].push_back(s[i][j - 1]);
                            while(j< l && a[s[i][j]][p] == a[s[i][j - 1]][p]){
                                tmp[a[s[i][j]][p] - 'a'].push_back(s[i][j]);
                                j++;
                            }
                        }
                    }
                }
            }
            for(int i = 0; i < 26;i++){
                s[i] = tmp[i];
                tmp[i].clear();
            }
             //for(int i = 0; i < 26; i++)
            // printf("%d:%d\n", i,s[i].size());
        }
        p++;
    }
    printf("%d",ans);
    return 0;
}