Official

B - Blocks on Grid Editorial by kyopro_friends


グリッド全体の最小値に揃えるのが最善です。

最初に最小値を求め、各要素から最小値を引いたものの和を計算すればよいです。

実装例(C)

#include<stdio.h>

int a[110][110];
int main(){
	int h,w;
	scanf("%d%d",&h,&w);
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)scanf("%d",&a[i][j]);
	int m=1e9;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)if(m>a[i][j])m=a[i][j];
	int ans=0;
	for(int i=0;i<h;i++)for(int j=0;j<w;j++)ans+=a[i][j]-m;
	printf("%d\n",ans);
}

実装例(Python)

import numpy as np
H,W = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(H)]
A = np.array(A)
print(np.sum(A-np.min(A)))

なお、この問題は空間計算量 \(O(1)\) で解くこともできます。

posted:
last update: