終了後に復習参加。
https://www.hackerrank.com/contests/camypapercon01/challenges/painting-bricks
問題
縦横1cm、高さH[i]cmのN個のブロックがあり、水平な地面の上に立っている。
各ブロックの向きは固定である。
これらのブロックを任意の順で手前から奥に(前後の面が接するように)並べていく。
各ブロックのうちある同じ1面を紫、別の同じ1面を黄色で塗ったとき、ブロック群を並べた後連結した図形について、紫の面と黄色の面の面積差の最大値を求めよ。
解法
紫の面を最大化するには、左か右の面を紫にすればよく、その面積はsum(H)cm^2。
黄色の面の最小面積は、以下の何れかである。
- 上の面を塗ったとき、N(cm^2)となる。
- ブロックを高い順に並べたとき、手前の面を塗るとmax(H)cm^2
よって解はsum(H)-min(N,max(H))。
int N; int H[101]; int tot; void solve() { int i,j,k,l,r,x,y; string s; cin>>N; FOR(i,N) cin>>H[i], tot+=H[i]; sort(H,H+N); cout<<max(tot-H[N-1],tot-N)<<endl; }
まとめ
ここらへんはまだ簡単。