# PKU POJ 3757 Simple Distributed storage system 解题报告

n，k为整数

f，pi，bi，ci为实数

$$sci = fi \times ci$$(1)

$$time = \frac{fi}{pi} + \frac{fi}{bi}$$(2)

$$\sum_{i=1}^{k} fi = f$$(3)

$$fi = \frac{time \times pi \times bi}{pi + bi}$$ {4}

$$time \times (\sum_{i=1}^{k} \frac{pi \times bi}{pi + bi}) = f$$(5)

=> $$sci = \frac{f}{sPar1} \times pi \times bi \times \frac{ci}{pi + bi}$$(6)

=> $$Sum(sci) = \frac{f \times sPar2}{sPar1}$$(7)

$$res = f \times \frac{\sum_{i=1}^{k} xici}{\sum_{i=1}^{k} xi}$$

z(l) > 0 when l < l* z(l) = 0 when l = l* z(l) < 0 when l > l*

/**
* URL:http://acm.pku.edu.cn/JudgeOnline/problem?id=3757
* Author: OWenT
* 0-1分数规划，特殊排序，二分
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define MAXN 20005
typedef struct
{
double p,b,c;
double pb,pbc;
}bank;

bank bk[MAXN];
double br,bl,bm;// for binary search
double f;// file size

bool cmp(bank a, bank b)
{
return f * a.pbc - bm * a.pb < f * b.pbc - bm * b.pb;
}

double getZFun(const long &k);

int main()
{
long k,n,i;
double res;

scanf("%ld %ld", &n, &k);
scanf("%lf", &f);

for(i = 1; i <= n; i ++)
{
scanf("%lf %lf %lf", &bk[i].p, &bk[i].b, &bk[i].c);
bk[i].pb = bk[i].b * bk[i].p / (bk[i].b + bk[i].p);
bk[i].pbc = bk[i].pb * bk[i].c;
}

//binary search
br = 1e10 + 1;
bl = 0;
while(br - bl > 1e-6)
{
bm = (br + bl) / 2;
sort(bk + 1, bk + n + 1, cmp);
double tmp = getZFun(k);
if(tmp > 0)
bl = bm + 1e-6;
else
br = bm - 1e-6;
}

res = bl;
printf("%.4lf\n", res);
return 0;
}

double getZFun(const long &k)
{
long i;
double sum = 0;
for(i = 1; i <= k; i ++)
sum += f * bk[i].pbc - bm * bk[i].pb;

return sum;
}

（该迭代的过程中出现了一个白痴级别的小问题，搞得我WA了无数次，不爽）

/**
* URL:http://acm.pku.edu.cn/JudgeOnline/problem?id=3757
* Author: OWenT
* 0-1分数规划，特殊排序，二分
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;

#define MAXN 20005
typedef struct
{
double p,b,c;
double pb,pbc;
double sortPar;
}bank;

bank bk[MAXN];

bool cmp(bank a, bank b)
{
return a.sortPar - b.sortPar < 1e-8;
}

int main()
{
long k,n,i;
double f, res, tmpRes;

scanf("%ld %ld", &n, &k);
scanf("%lf", &f);

for(i = 1; i <= n; i ++)
{
scanf("%lf %lf %lf", &bk[i].p, &bk[i].b, &bk[i].c);
bk[i].pb = bk[i].b * bk[i].p / (bk[i].b + bk[i].p);
bk[i].pbc = bk[i].pb * bk[i].c;
}

//更快的迭代
res = 0;
tmpRes = 1e10;
while(fabs(res - tmpRes) > 1e-6)
{
for(i = 1; i <= n; i ++)
bk[i].sortPar = f * bk[i].pbc - res * bk[i].pb;
tmpRes = res;
sort(bk + 1, bk + n + 1, cmp);
double tmpA = 0, tmpB = 0;
for(i = 1; i <= k; i ++)
{
tmpA += f * bk[i].pbc;
tmpB += bk[i].pb;
}
res = tmpA / tmpB;
}

printf("%.4lf\n", tmpRes);
return 0;
}

167 篇文章28 人订阅

0 条评论

## 相关文章

44440

15330

22930

22680

233100

1.9K00

### 百度云部门 C++面试

14）读套接口时候返回0，时候时候产生EAGIN。【EAGIN也不太清楚，知道又这个玩意，不知道具体的，应该直接说不知道】

17020

10330

222100

10140