TopCoderOpen 2016 Round1A Medium: EllysSocks

問題概要

各靴下の長さS[]と、ペアにしたい数Pが与えられる。max(ペアにした靴下の長さの差)の最小値を求めよ。

解法

まず、与えられた靴下の長さをソートすると、靴下のペアは隣り合ったもの同士で作るのが最良であることがわかるので、許容できる靴下の長さの差を二分探索で求めればよいです。

コード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;

class EllysSocks {
public:

  int N;
  vector<int> S;
  int P;
  
  bool check(int d){
    int p = 0;
    for(int i = 0; i < N-1; i++){
      if(S[i+1] - S[i] <= d){
	p++;
	i++;
      }
    }
    return p >= P;
  }

  int getDifference(vector<int> _S, int _P) {
    
    S = _S; P = _P;
    N = S.size();

    sort(S.begin(), S.end());

    int l = -1, r = 1000000000;

    while(r - l > 1){

      int mid = (r+l)/2;

      if(check(mid)){
	r = mid;
      }
      else
	l = mid;
      
    }

    return r;

  }
};