問題
http://community.topcoder.com/stat?c=problem_statement&pm=11454&rd=15037
ワーカーが複数存在し、それぞれのワーカーi について以下がわかっている。
a[i]:１時間あたりにこなせる仕事の数
p[i]:仕事あたりにかかるコスト
今回、ワーカーから複数人選び、同じ時間働くように均等に仕事を割り当てる。
こなしたい仕事の数がわかっているとき、必要な最小コストを求める。
解き方
サンプル通りの計算だとワーカーiにタスクtを割り当てた時のコストは
t[i]*3600/a[i]となる。
ここで時間が均等になるようtを割り当てるのは計算が難しいので
考え方を変える。
ｘ時間を均等に割り当てたとき、
コスト ：x*(a[i]*p[i] + a[j]*p[j]...+3600K)
タスク数：x*(a[i]+a[j]...)
単純にするために１時間の場合を考えると
コスト ：a[i]*p[i] + a[j]*p[j]...+3600K
タスク数：a[i]+a[j]...
ここで、求めたい最小のコストansは
ans/totalwork*(a[i]+a[j]...)>=a[i]*p[i] + a[j]*p[j]...+3600K
を満たす最小のansとなる。
ここで１タスクあたりの最小コストM=ans/totalworkとおくと、
M*(a[i]+a[j]...)>=a[i]*p[i] + a[j]*p[j]...+3600K
よって上記式を満たす最小のMを求め、totalWorkをかけてあげればよい。
最適なワーカーはa[i]*(M-p[i])の昇順で選ぶことができる。
コード
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 FoxAndBusiness {
public: double minimumCost(int K, int totalWork, vector<int> a, vector<int> p) {
int n=a.size();
double low=0.0,high=1e+20;
FORE(x,0,1000){
double mid=(high+low)/2;
vector<double> vx;
FORE(i,0,n)vx.push_back(a[i]*(p[i]-mid));
sort(all(vx));
double sum=K*3600;
FORE(i,0,K)sum+=vx[i];
if(sum<=0)high=mid;
else low=mid;
}
return high*totalWork;
}
};
#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 FoxAndBusiness {
public: double minimumCost(int K, int totalWork, vector<int> a, vector<int> p) {
int n=a.size();
double low=0.0,high=1e+20;
FORE(x,0,1000){
double mid=(high+low)/2;
vector<double> vx;
FORE(i,0,n)vx.push_back(a[i]*(p[i]-mid));
sort(all(vx));
double sum=K*3600;
FORE(i,0,K)sum+=vx[i];
if(sum<=0)high=mid;
else low=mid;
}
return high*totalWork;
}
};