https://atcoder.jp/contests/abc296/tasks/abc296_d
时间: 2023-09-25 12:11:39 浏览: 88
【問題概要】
縦 $H$ 行、横 $W$ 列のマスがあります。 上から $i$ 行目、左から $j$ 列目のマスを $(i,j)$ とします。
最初、すべてのマスは白色であり、マス $(i,j)$ は $C_{i,j}$ という文字が書かれています。
あなたは、以下の操作を好きな回数だけ行うことができます。
操作: 黒色を塗られたマス $(i,j)$ を選び、以下のいずれかの操作を行う。
(1) $C_{i,j}$ を $1$ 減らす。
(2) $C_{i,j}$ を $1$ 増やす。
ただし、この操作を行う際には、必ずしも $C_{i,j}$ が $0$ 以上である必要はありません。
操作後、すべてのマスが白色になっている場合、操作回数の最小値を求めてください。
【制約】
・$1 \leq H,W \leq 50$
・$0 \leq C_{i,j} \leq 10^{9}$
・$C_{i,j}$ は整数である。
・少なくとも $1$ つのマスには文字が書かれている。
【入力】
入力は以下の形式で標準入力から与えられる。
$H$ $W$
$C_{1,1}$ $C_{1,2}$ ... $C_{1,W}$
$C_{2,1}$ $C_{2,2}$ ... $C_{2,W}$
...
$C_{H,1}$ $C_{H,2}$ ... $C_{H,W}$
【出力】
操作回数の最小値を出力せよ。
【入力例】
3 3
3 1 4
1 5 9
2 6 5
【出力例】
2
【入力例】
3 3
1 1 1
1 1 1
1 1 1
【出力例】
0
【入力例】
4 4
0 0 1 0
1 0 0 0
0 0 0 0
0 0 0 1
【出力例】
2
【入力例】
5 5
0 0 1 0 0
1 1 1 1 1
0 0 0 0 0
1 1 1 1 1
0 0 1 0 0
【出力例】
0
【解法】
まず、全体の合計を求めます。
次に、全体の合計が $0$ の場合、操作回数は $0$ となります。
全体の合計が $1$ 以上の場合、以下の操作を行います。
1. 全体の合計を $2$ で割り、切り捨てた値を $S$ とします。
2. 全体の合計が奇数の場合、$S$ を $1$ 増やします。
3. 以下の操作を繰り返します。
1. 最大値を取るマスを選び、そのマスの値を $2$ 減らします。
2. 上記操作によって、全体の合計が $S$ 以下になる場合、操作回数を出力して終了します。
上記操作によって、全体の合計が $S$ 以下になることが証明できます。
また、上記操作によって操作回数が最小になることが証明できます。
【コード】
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)