SRM647div1easy:BuildingTowersEasy

これは簡単なのでコードだけ。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13634&rd=16279

const int INF = 1e9;

bool ok(int pos, int h, const vector<int>& x, const vector<int>& t) {
    if (h > pos-1) return false;
    int n = x.size();
    for (int i = 0; i < n; i++) {
        if (t[i] + abs(pos-x[i]) < h) return false;
    }
    return true;
}

class BuildingTowersEasy {
public:
    int maxHeight(int N, vector <int> x, vector <int> t) {
        int ret = 0;
        for (int i = 1; i <= N; i++) {
            int low = 0, high = INF;
            while (high - low > 1) {
                int med = (high + low) / 2;
                if (ok(i, med, x, t)) low = med;
                else high = med;
            }
            ret = max(ret, low);
        }
        return ret;
    }
};