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

题目链接：<http://acm.pku.edu.cn/JudgeOnline/problem?id=3757>

题目大意

第一行输入n，k，f表示从n个服务器里选k个，传输大小为f（以Mb为单位）的文件

接下来输入每个服务器的吞吐量，带宽和资源消耗（pi，bi，ci）

传输数据的总时间=传输的大小(fi)/pi+fi/bi

传输每Mb消耗的资源为ci

要求每台服务器完成传输的时间相同

求最小的资源消耗和Sum(sci)【sci=fi\*ci】

输出是一行：Min{Sum(sci)}

输入数据

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)

令 $$sPar1 = \sum\_{i=1}^{k} \frac{pi \times bi}{pi + bi}$$

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

令 $$sPar2 = \sum\_{i=1}^{k} \frac{pi \times bi \times ci}{pi + bi}$$

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

以上是我做题时的思路尽头，后来看了某个大牛的代码，再看了点关于0-1分数规划的资料有了下一步整理

关于0-1分数规划：

令 $$xi = \frac{pi \times bi}{pi + bi}$$

现在我们知道

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

令 $$z = \min (f \times (\sum\_{i=1}^{k} xici) - res \times (\sum\_{i=1}^{k} xi) )$$

即 $$z(l) = \min ( f \times (\sum\_{i=1}^{k} xici) - l \times (\sum\_{i=1}^{k} xi) )$$

由于z(l)单调递减,设问题最优解为l\*

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

然后只要二分算出l使得z(l) = 0即可。其中min的部分可以排序解决

代码：

```cpp
/**
 * 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;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.owent.net/2010/41.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.