lay_contest beta round 00004 : B - 神による整地 (2)

(4)は真面目にやらずに離脱。(3)までは解けたので良かったね。
https://www.hackerrank.com/contests/lay-contest-00004/challenges/2-12

問題

H*Wのグリッド状の敷地について、各セルの高さH[r][c]が与えられる。
各セルの高さを1上げるにはコストA、1下げるにはコストB、１か所を1上げ別の場所を下げるにはコストGかかる。
全セルの高さを揃えるのにかかる最小コストを求めよ。

解法

Hの範囲は狭いので、min(H)～max(H)の範囲でそろえる高さを総当たりしよう。
揃える高さhが決まると、Hを事前にソートしておくことで、hより高さが大きいセルなので減らさないといけない高さの総和sumDと、高さが小さいセルなので増さないといけない高さの総和sumIが求まる。
G＜A+Bならmin(sumD,sumI)分だけコストGによる高さの増減を行い、残った高さはコストA,Bの手段で高さを均せばよい。

int T;
int H,W,N;
ll A,B,G;
ll HH[10101];
ll S[10101];

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>T;
	while(T--) {
		cin>>H>>W>>A>>B>>G;
		N=H*W;
		FOR(x,N) cin>>HH[x];
		sort(HH,HH+N);
		FOR(x,N) S[x+1]=S[x]+HH[x];
		
		ll ret=1LL<<60;
		for(i=-100000;i<=100000;i++) {
			j=lower_bound(HH,HH+N,i)-HH;
			ll pl=(S[N]-S[j])-1LL*i*(N-j);
			ll mi=1LL*i*j-(S[j]-S[0]);
			ll tot=0;
			if(A+B>G) {
				ll a=min(pl,mi);
				tot += G*a;
				pl-=a;
				mi-=a;
			}
			tot += A*mi+B*pl;
			ret=min(ret,tot);
		}
		
		cout<<ret<<endl;
	}
}

まとめ

またこれ何かのゲームが元ネタだったりするのかな。
ポピュラスとかシムシティとか…でも増減を同時に行うオペレーションってなさそう。