yukicoder No.198 キャンディー・ボックス2
問題概要
省略
解法
それぞれの箱にいれる数を決めると、作業の回数が決まる。求めるものは作業回数の最小値。すこし考えると、仮にそれぞれの箱にx個入れた時が答えとなるとすると、x個以下でそろえようとしたときは、作業回数は増え、またx個以上でそろえようとした時も作業回数は増える。このことから、下凸の関数になっていることがわかる。よって三分探索を行うことで、xを求められるので、その時の作業回数が答えとなる。
三分探索するときに注意しなければならないことは、今回はそれぞれの箱にいれる数を0にして、すべてなくすことは可能であるが、手持ちのキャンディーに制限があるので、それそれの箱にいれる数には制限がある。箱から取り出したキャンディーは手持ちのキャンディーになるので、
(それぞれの箱に入れられる上限) = (箱に入っているキャンディーの合計 + b) / n
となる。これらを考慮すると、三分探索のはじめの左端は0、右端は上の式でだした上限で始めればよいことになる。また、最初に箱に入っているキャンディーの中で最小値より少ない値で、作業回数が最小値となることはないので、左端は、箱に入っている数の中で最小値にした。
ミス
三分探索はバグらしちゃう。
コード
#include <iostream> #include <cstdio> #include <string> #include <vector> #include <cmath> #include <algorithm> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) #define reps(i,f,n) for(int i=(f);i<(n);i++) const ll INF = 1e18; ll b; vector<ll> c; int n; ll search(ll m){ ll cnt = 0; rep(i, n){ cnt += abs(m - c[i]); } return cnt; } int main(void){ cin >> b >> n; ll sum = b; rep(i, n){ ll t; cin >> t; c.push_back(t); sum += t; } if(n == 1){ printf("0\n"); return 0; } sort(c.begin(), c.end()); //下凸関数を三分探索 ll l = c[0]; ll r = sum / n + 1; while(r - l > 3){ ll m1 = (l * 2 + r) / 3; ll m2 = (l + r * 2) / 3; if(search(m1) > search(m2)){//左側が高い l = m1; }else{//右側が高い r = m2; } } ll ans = INF; for (int i = l; i < r; ++i){ ans = min(ans, search(i)); } printf("%lld\n", ans); return 0; }