SRM 613 Div1 250 TaroFriends

2014-03-23

00:38 |

直線上の猫の座標 C[i] が最大 50 個与えられる。各自 +X か -X にゃー(動く)。一番左の猫と一番右の猫の座標の差の最小値を求めよ。
|C[i]|≦10^8, 0≦X≦10^8

一番左(または右)の猫の座標は最大でも100通りしかないのがポイント。
一番左の座標 left を決めたら、全ての猫を left を下回らないようにできるだけ左に動かせばいい。
左がだめなら右に動かす。それもだめならその left はだめ。
置けた left の中で差が最小のものが答え。
毎回こんな 250 ならいいのに。

accepted

class TaroFriends {
	public:
	int getNumber(vector <int> C, int X) {
		ll ans = 1<<30;
		REP(i, C.size()) {
			REP(j, 2) {
				int ok=1;
				ll lans = 0;
				ll left = C[i] + (j?-X:X);
				REP(k, C.size()) {
					if(left <= C[k]-X) lans=max(lans, abs(C[k]-X - left));
					else if(left <= C[k]+X) lans=max(lans, abs(C[k]+X - left));
					else ok=0;
				}
				if(ok) ans=min(ans, lans);
			}
		}
		return ans;
	}
};