华为面试题(8分钟写出代码)

有两个数组a,b，大小都为n,数组元素的值任意，无序；

要求：通过交换a,b中的元素，使数组a元素的和与数组b元素的和之间的差最小

题目来源：http://bbs.chinaunix.net/thread-855126-1-1.html

#include<array>
#include<random>
#include<algorithm>
#include<cmath>
#include<iostream>

template<class T, size_t N>
std::ostream& operator<<(std::ostream &ostr, std::array<T, N> const &data){
 for (size_t i = 0; i != N; ++i) ostr << data[i] << " ";
 return ostr;
}

int main(){
 using type = int;
 size_t const n = 3;
 std::array<type, n> a, b;
 
 std::mt19937 gen((std::random_device())());
 std::uniform_int_distribution<type> rand(0, n*n);// 小心溢出
 
 for (size_t i = 0; i != n; ++i) {
  a[i] = rand(gen);
  b[i] = rand(gen);
 }
 
 type delta = 0;
 for (size_t i = 0; i != n; ++i){
  delta += a[i] - b[i];
 }
 type abs_delta = std::abs(delta);
 std::cout << a << "\n" << b << "\ndelta = " << abs_delta << "\n";

 size_t step = 0;
 do{
  ++step;
  type delta_2 = delta, abs_delta_2 = abs_delta;
  size_t i0, j0;
  for (size_t i = 0; i != n; ++i){
   for (size_t j = 0; j != n; ++j){
    type tmp = a[i] - b[j], tmp_delta = delta - tmp*2, abs_tmp_delta = std::abs(tmp_delta);
    if (abs_tmp_delta < abs_delta_2){
     delta_2 = tmp_delta;
     abs_delta_2 = abs_tmp_delta;
     i0 = i;
     j0 = j;
    }
   }
  }
  if (abs_delta_2 < abs_delta){
   std::swap(a[i0], b[j0]);
   delta = delta_2;
   abs_delta = abs_delta_2;

   std::cout << "\nstep " << step << ": swap(" << i0 << ", " << j0 << ")\n" << a << "\n" << b << "\ndelta = " << abs_delta << "\n";
  }
  else{
   break;
  }
 } while (true);
 
 return 0;
}