土下座しながら探索中

主に競技プログラミング

UVa 1577 : Low Power

問題リンク :
https://uva.onlinejudge.org/external/15/1577.pdf

問題概要 :
n台のマシーンがある
各マシーンは2つの回路を持っていて、
各回路はk個のバッテリーを持っている
つまり、全てのマシーンにバッテリーをセットするためには2*n*k個のバッテリーが必要となる
また、バッテリーのパワーは整数として表される
各マシーンにバッテリーをセットしたい
マシーンにバッテリーをセットすると、2つの回路内のバッテリーのパワーの最小値の差分が出力される
各マシーンが出力する値の最大値を最小化するようにバッテリーをマシーンにセットし、その値を出力せよ

解法 :
二分探索
バッテリーはパワーが小さい順にソートしておく
二分探索で最大値の最小値xを決める
xを決めたとき、最大値の最小値がx以下になるようにバッテリーをセットできるかチェックする
これは前から貪欲に回路の最小値のペアを作っていくことでチェックできる
バッテリーのうち一番小さい値は必ず回路の最小値となる
その値の次の値と差分をとったときに、差分がx以下ならそれらを2つの回路の最小値とする
そうでないなら今一番小さい値は前の回路のいずれかに入れてしまう

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

int n,k,p[1000100];

bool check(int maxi_diff) {
  int remain = 0;
  int pair_cnt = 0;
  rep(i,2*n*k) {
     //iとi+1を回路の最小値とする
     //iとi+2を最小値のペアとしないのは、そうした場合i+1がi+3以降とペアになる必要がでてきて、
     //i+2が存在しない分だけその差分が離れてしまうから、それだったらiとi+1をペアにしたほうが良い
    if( pair_cnt < n && i+1 < 2*n*k && p[i+1]-p[i] <= maxi_diff ) {
      remain += ( k - 1 ) * 2;
      ++pair_cnt, ++i;
    } else {
      if( remain ) --remain;
      else         return false;
    }
  }
  return true;
}

void compute() {
  sort(p,p+2*n*k);
  int L = 0, R = p[2*n*k-1]-p[0];
  while( L + 1 < R ){
    int M = ( L + R ) / 2;
    if( check(M) ) R = M;
    else           L = M;
  }
  if( check(L) ) printf("%d\n",L);
  else if( check((L+R)/2) ) printf("%d\n",(L+R)/2);
  else printf("%d\n",R);
}

int main() {
  while( scanf("%d %d",&n,&k) != EOF ) {
    rep(i,2*n*k) scanf("%d",p+i);
    compute();
  }
  return 0;
}