比赛时候无人ac赛后我过掉了。感觉还是一个很不错的分数规划,主要精髓在第一步的分数式转换上。
题目是POJ3757。
开始看题感觉头疼的地方是要求同时完成。这里有一个很精髓的转换,把流量换为速度。假设最终时间为t,那么对于每个被选中的服务器,速度vi=fi/t=bp/(b+p),两边求和t=sigma(fi)/sigma(vi)=F/sigma(vi),然后最后要求总花费最小,每个被选中的服务器的花费为fi*ci=vi*ti*ci。两个式子有可以推出对于选出的K个服务器,
sigma(vi*ti)=sigma(fi)=F,sigma(fi*ci)=sigma(vi*ti*ci),将ti=F/sigma(vi)带入式子。总花费cost=F*sigma(vi*ci)/sigma(vi),这样就转换成了标准的分数规划了~
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
code
1
#include <iostream>
2
#include <cstdio>
3
#include <algorithm>
4
#include <cstring>
5
#include <cmath>
6
using namespace std;
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
int N,K;
9
double F,ans;
10![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
11![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
struct Sever
{
12
double pi,bi,ci,xi,vi,value;
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
bool operator < (const Sever &A) const
{
14
return value<A.value;
15
}
16
}sever[20005];
17![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
18![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
bool bigger(double mid)
{
19
int i;
20![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0;i<N;i++)
{
21
sever[i].value=F*sever[i].xi-mid*sever[i].vi;
22
}
23
sort(sever,sever+N);
24
double sum=0;
25![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0;i<K;i++)
{
26
sum+=sever[i].value;
27
}
28
if(sum<0) return true;
29
return false;
30
}
31![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
32![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
int main()
{
33
scanf("%d%d",&N,&K);
34
scanf("%lf",&F);
35
int i;
36![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
for(i=0;i<N;i++)
{
37
scanf("%lf%lf%lf",&sever[i].pi,&sever[i].bi,&sever[i].ci);
38
sever[i].vi=sever[i].bi*sever[i].pi/(sever[i].pi+sever[i].bi);
39
sever[i].xi=sever[i].vi*sever[i].ci;
40
}
41
double l=0.0,r=1e10+1,mid;
42![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
while(r-l>1e-5)
{
43
mid=(l+r)/2;
44![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
if(bigger(mid))
{
45
r=mid;
46
}
47![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
else
{
48
l=mid;
49
}
50
}
51
printf("%.4lf\n",mid);
52
return 0;
53
}
54![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2010-08-02 11:14
OpenWings 阅读(169)
评论(0) 编辑 收藏 引用