区間探索

二分探索のみ

code: Interval.js

class Interval {

/* 関数が最後にtrueになる整数値を返します */

/* reverse = trueの場合,最初にtrueになる整数値を返します */

static findIntBoundary(lower,upper,func,reverse) {

if (reverse == null) { reverse = false; }

if (upper - lower <= 1) { return reverse ? upper : lower; }

const mid = ((lower + upper) / 2)|0;

if (func(mid) !== reverse) { return Interval.findIntBoundary(mid,upper,func,reverse); }

return Interval.findIntBoundary(lower,mid,func,reverse);

}

/* 関数が最後にtrueになる浮動小数点値を返します */

static findFloatBoundary(lower,upper,eps,func, reverse) {

if (reverse == null) { reverse = false; }

if (upper - lower < eps) { return (lower + upper) / 2; }

const mid = ((lower + upper) / 2);

if (func(mid) !== reverse) { return Interval.floatBinSearch(mid,upper,eps,func); }

return Interval.floatBinSearch(lower,mid,eps,func);

}

}

サンプル

yahoo-procon2017-final-open

code: yah_b.js

class Main {

solve() {

const arr = input.nextIntArr();

const teamN = _.sort(input.nextIntArr());

const teamM = _.sort(input.nextIntArr());

const upper = Math.max(_.last(teamN),_.last(teamM));

const lower = -1;

const func = (x) => {

let j = teamM.length - 1;

let k = 0;

if (j < 0) { break; }

++k;

--j;

}

}

console.log(Interval.findIntBoundary(lower,upper,func,true));

}

}