Removing Columns - CodeForces 496 C 【暴力+贪心】

题意：给定n个长度相同的字符串。求最少的执行操作。要求下一行的字典序不小于上一行的字典序。 操作是：删除任意一列。

数据分析：1 ≤ n, m ≤ 100 （n=1时，输出0）

思路：比较下一行与上一行的字典序，然后用vis来标记某一列是不是删除过。对于mp[i][j]和mp[i-1][j]，如果相等，那么继续查找下一列；如果前者大，break；否则ans++ ， vis[j]=true

// 感觉这题所谓的贪心，感觉不够贪，纯暴力

复杂度分析：O(m*n*m)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char mp[200][200];
bool vis[200];

int main(void)
{
    memset(vis,false,sizeof(vis));
    int n,m;
    cin >> n>>m;
    for(int i=1; i<=n; i++)
        scanf("%s",mp[i]+1);
    if(n==1)
    {
        printf("0\n");
        return 0;
    }
    ll ans=0;
    int t=m;
    while(t--)//执行t次。因为最多就只需要重头扫到尾m次最多了。
    {
        for(int i=2; i<=n; i++)
        {
            for(int j=1; j<=m; j++)
            {
                if(vis[j]==true || mp[i-1][j]==mp[i][j])    continue;
                if(mp[i-1][j]<mp[i][j])    break;
                else if(mp[i-1][j]>mp[i][j])
                {
                    vis[j]=true;
                    ans++;
                    //printf("i=%d j=%d\n",i,j);
                }
            }
        }
    }
    cout << ans << endl;
}