首页 > 代码库 > GCJ——Crazy Rows (2009 Round 2 A)

GCJ——Crazy Rows (2009 Round 2 A)

题意:

  给定一个N*N的矩阵,由0,1组成,只允许交换相邻的两行,把矩阵转化为下三角矩阵(对角线上方全是0),最少需要多少次交换?(保证可以转化为下三角矩阵)

Large:

  N<=40

解析:

  假如每一行的1的个数都是不相同的,即,最终答案中的矩阵是唯一的,这就相当于求对给定数组冒泡排序需要几次交换一样。但显然,题目没有如此保证。

  方法是贪心法:(策略不给出证明)

    从第一行到最后一行依次满足,因为可以满足前面行的也一定可以满足后面的,所以每次只需要找到可以满足当前行的最近的就可以了。

  预处理最后一个1的位置的话,时间复杂度是N^2

GCJ——Crazy Rows (2009 Round 2 A)