2211 迷い猫、走った

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2211&lang=jp

方針

最大値を最小化する問題なので、2分探索すればいいのはすぐにわかる。
けれども、ある猫の数以下で条件を満たすことができるかどうかの判定が難しい。
解説のスライドを見ても、なかなか分からなかった。

ソース

#include<iostream>
#include<map>
#include<algorithm>
#include<cassert>
#include<vector>
#include<cstring>
using namespace std;

int dp[1000], catsum[20010];
vector<pair< int, int > > cats;
vector<int> foods;
int N,M,lmost;

bool isable(int mid) {
    memset(dp, -1, sizeof(dp));
    dp[M-1] = 0;

    for(int i=M-2; i>=0; --i) {
        int ret = 1<<29;
        for(int j=i+1; j<M; ++j) {
            int right = catsum[foods[j]] - catsum[(foods[i]+foods[j])/2];;
            int left = catsum[(foods[i]+foods[j])/2] - catsum[foods[i]];

            if(right + dp[j] <= mid) ret = min(left, ret);
        }
        dp[i] = ret;
    }
    if(dp[0] + catsum[foods[0]] <= mid) return true;
    return false;
}

int main() {
    int x,y,c,totalcats = 0;
    while(cin>>N>>M, N|M) {

        memset(catsum, 0, sizeof(catsum));
        foods.clear();
        cats.clear();
        totalcats = 0;

        for(int i=0; i<N; ++i) {
            cin>>x>>y>>c;
            x += 10000;
            totalcats += c;
            cats.push_back(make_pair(x,c));
        }

        for(int i=0; i<M; ++i) {
            cin>>c;
            foods.push_back(c+10000);
        }

        sort(cats.begin(), cats.end());
        sort(foods.begin(), foods.end());

        for(int i=0; i<N; ++i) {
            if(cats[i].first <= foods[0]) cats[i].first = foods[0];
            if(cats[i].first >= foods[M-1]) cats[i].first = foods[M-1];
            catsum[cats[i].first] += cats[i].second;
        }

        for(int i=0,ss = 0; i<20010; ++i) {
            ss += catsum[i];
            catsum[i] = ss;
        }

        int low = -1,hi = totalcats;
        while(low+1<hi) {
            int mid = (low+hi)/2;
            if(isable(mid)) hi = mid;
            else low = mid;
        }
        cout<<hi<<endl;
    }
}