19湖南G

/*解题思路：
我们容易想到一个n^3的贪心：每次找到最小的可以放进来的第j列，同时记录当前连续的依然相等的行。第j列可以放进来的条件为：对于当前每一个依然相等的连续行(i,i+1)(i,i+1)(i,i+1)，有C[i][j]&lt;=C[i+1][j]C[i][j] &lt;= C[i+1][j]C[i][j]<=C[i+1][j]。
一共要找m次列，每次找列是枚举m个列，而检查列是否符合条件需要检查当前所有依然相等的连续行，最差情况下要检查n次。总的复杂度O(m2n)O(m^2n)O(m
2
 n)，肯定是不行的。考虑优化其中的一个步骤。
想到优化检查这一步，不是暴力检查，而是用cnt[j]cnt[j]cnt[j]记录第jjj列有多少行满足（C[i][j]>C[i+1][j]）（C[i][j] &gt; C[i+1][j]）（C[i][j]>C[i+1][j]）。如果为0，则表示这一列可以加入。这样把检查优化到了O(1)，但是每一次加入一列之后要去更新其他没加入的列的cntcntcnt。
什么情况下一列的cnt会减少？也就是什么情况下对于还没放入的第j列，(C[i][j]>C[i+1][j])(C[i][j] &gt; C[i+1][j])(C[i][j]>C[i+1][j])的影响被消除？
只要前面放入的列中，有一列k满足(C[i][k]&lt;C[i+1][k])(C[i][k]&lt;C[i+1][k])(C[i][k]<C[i+1][k]),那么(C[i][j]>C[i+1][j])(C[i][j] &gt; C[i+1][j])(C[i][j]>C[i+1][j])对于第j列的影响就被消除了。
记录当前依然相等的连续行，加入新的一列j时，如果第j列可以把某连续行(i,i+1)分开（也就是C[i][j]<C[i+1][j])，那么就更新剩余列的cnt。因为只更新连续行，最多更新n次（一共就n行，每更新一次最少会少1个连续行），更新一次的复杂度是O(m)。
总的复杂度为O(m2+nm)O(m^2+nm)O(m
2
 +nm)

代码：
————————————————
版权声明：本文为CSDN博主「_ 泛白」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43202683/article/details/100170570
*/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 2e3 + 50;
int n, m;
int c[maxn][maxn];
int cnt[maxn];// 有多少个不符合条件的
int dif[maxn];//dif[i]=1 表示第i行和i+1行已经不相等了
int vis[maxn];
void init(){
    memset(cnt, 0, (m+1)<<2);
    memset(vis, 0, (m+1)<<2);
    memset(dif, 0, (n+1)<<2);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m ;++j){
            scanf("%d", &c[i][j]);
            if(i!=1){
                cnt[j] += (c[i-1][j] > c[i][j]);
            }
        }
    }
}
vector<int> ans;
void sol(){
    ans.clear();
    while(ans.size() < m){
        int j;
        for(j = 1; j <= m; ++j){
            if(vis[j] || cnt[j] > 0) continue;
            break;
        }
        if(j > m){//没找到
            printf("-1\n"); return;
        }
        ans.push_back(j);
        vis[j] = 1;
        for(int i = 1; i < n; ++i){
            if(dif[i]) continue;
            if(c[i][j] >= c[i+1][j]) continue;
            dif[i] = 1;
            for(int k = 1; k <= m; ++k){
                if(c[i][k] > c[i+1][k]) cnt[k]--;
            }
        }
    }
    for(int i = 0; i < ans.size(); ++i){
        if(i > 0) printf(" ");
        printf("%d", ans[i]);
    }printf("\n");
}
int main()
{
    while(scanf("%d%d", &n, &m)!=EOF){
        init();sol();
    }
}

————————————————
版权声明：本文为CSDN博主「_ 泛白」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_43202683/article/details/100170570