問題
http://community.topcoder.com/stat?c=problem_statement&pm=12779&rd=15705
複数のペットがおり、各ペットごとにトラックを走りきる最小の時間と最大の時間が与えられる。
ペットを２つのチームに分けてチームごとに競争させ、２つのチームのゴール時間ができるだけ均衡するようにしたい。
このとき、２チーム間のゴール時間の差の最小を求める。
解き方
２つのチームをそれぞれＳ，Ｔとしたとき、
Ｓの最小とＴの最大の差、Ｓの最大とＴの最小の差のうち大きい方が答えになる。
各ペットの最小時間の集合をＡ，最大時間の集合をＢとしたとき、
Ｓの最小とＴの最大の差は
|ΣA(s)ーΣB(t)|
(A(sum)-ΣA(t))-ΣB(t)
A(sum)-Σ(A(t)+B(t))
よって、Ａの合計からＴチームのA+Bを引いたものになる。
同様にＳの最大とＴの最小の差は
|ΣB(s)-ΣA(t)|
B(sum)-ΣA(s)-ΣA(t)
B(sum)-Σ(A(s)+A(t))
よって、Ｂの合計からＴチームのA+Bを引いたものになる。
あとは、全てのとりうるA+Bに対してAの合計とＢの合計との差を計算し、
最小の値が答えになる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MayTheBestPetWin {
public:
int calc(vector<int> A, vector<int> B) {
int n=A.size();
int suma=0,sumb=0;
FORE(i,0,n){
suma+=A[i];
sumb+=B[i];
}
int dp[suma+sumb+1];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,n){
for(int j=suma+sumb;j>=0;j--){
if(dp[j])dp[j+A[i]+B[i]]=1;
}
}
int ret=1e+9;
FORE(i,0,suma+sumb+1){
if(!dp[i])continue;
int cost=max(abs(suma-i),abs(sumb-i));
ret=min(ret,cost);
}
return ret;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class MayTheBestPetWin {
public:
int calc(vector<int> A, vector<int> B) {
int n=A.size();
int suma=0,sumb=0;
FORE(i,0,n){
suma+=A[i];
sumb+=B[i];
}
int dp[suma+sumb+1];
memset(dp,0,sizeof(dp));
dp[0]=1;
FORE(i,0,n){
for(int j=suma+sumb;j>=0;j--){
if(dp[j])dp[j+A[i]+B[i]]=1;
}
}
int ret=1e+9;
FORE(i,0,suma+sumb+1){
if(!dp[i])continue;
int cost=max(abs(suma-i),abs(sumb-i));
ret=min(ret,cost);
}
return ret;
}
};