LiveArchive 6306 - Smartphone Manufacturing

※ 未提出なので結果は不明。-> AC(2015/12/31)

問題概要

A,B,Cの3つの会社がある。それぞれの会社にはN人の社員がいて、各社員iにはスループットt_iが与えられる。以下の三つの条件のより上の条件を満たすように出力せよ。

1. 会社の全ての社員を使わなければならない。
2. 社員を2つのグループに分けたとき、グループ1の全ての社員のスループットの和と2の全ての社員のスループットの和の差を最小化せよ。
3. 全ての社員のスループットの総和を最大化せよ。

出力は、どの会社か、2つのグループに分けたときのスループットの和が小さい方、大きい方の順でする。

制約

• 2 ≤ N ≤ 1000
• 1 ≤ t_i ≤ 500

解法

この問題ではNが大きいので社員を2グループに分け、それぞれの和の差を最小化するのが最も難しい。この部分はDPをする。

コード

#include <bits/stdc++.h>

using namespace std;

struct State{
  int com,a,b,diff,sum;
  State(int c,int a,int b,int d,int s) :
    com(c),a(a),b(b),diff(d),sum(s) {}
  
  bool operator < (const State &s)const{
    if(diff != s.diff){
      return diff < s.diff;
    }else{
      return sum > s.sum;
    }
  }
};

int main(){
  int Tc,N,a;
  cin >> Tc;
  while(Tc--){
    vector<State> vec;
    for(int i = 0 ; i < 3 ; i++){
      cin >> N;
      int sum = 0;
      bool tab[1000001] = {false};
      tab[0] = true;
      for(int j = 0 ; j < N ; j++){
	cin >> a;
	for(int k = sum ; k >= 0 ; k--){
	  if(tab[k]) tab[k+a] = true;
	}
	sum += a;
      }
      a = sum / 2;
      for(; a >= 0 ; a--){
	if(tab[a]) break;
      }
      int b[2] = {a,sum-a};
      sort(b,b+2);
      vec.push_back(State(i,b[0],b[1],sum-a*2,sum));
    }
    sort(vec.begin(),vec.end());
    cout << (char)('A'+vec[0].com) << " " << vec[0].a << " " << vec[0].b << endl;
  }
  return 0;
}