CFR 803 A. Maximal Binary Matrix ( Greedy )
題意:
構造一個字典序最大的 N * N 的 01 矩陣,其中洽有 k 個 1,而且對於主對角線是對稱的。若不存在則輸出 -1。
制約:
The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 1e6).
解法:
首先若 K > N * N 顯然無解。
接著由上到下依序考慮每一排,先放一個在主對角線上,接著再兩個兩個放在排和列上。
時間 / 空間複雜度:
O( K ) / O( N^2 )
N, K = map( int, input().split() ) if K > N * N: exit( print( -1 ) ) G = [ [ 0 for i in range( N ) ] for j in range( N ) ] for i in range( N ): if K == 0: break G[ i ][ i ] = 1 K -= 1 for j in range( i + 1, N ): if K <= 1: break G[ i ][ j ], G[ j ][ i ] = 1, 1 K -= 2 for i in range( N ): print( ' '.join( str( v ) for v in G[ i ] ) )