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的部分可以排序解决

代码:

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏诸葛青云的专栏

教你利用Python把图片转字符画!代码哆啦A梦你见过嘛?

图片转字符画的关键是把图片的灰度值与自定义的字符集之间建立映射关系,不同区间的灰度值对应不同的字符,之后将图片每一个像素对应的字符打印出来,就是我们要的字符画。...

44440
来自专栏恰童鞋骚年

设计模式的征途—8.桥接(Bridge)模式

在现实生活中,我们常常会用到两种或多种类型的笔,比如毛笔和蜡笔。假设我们需要大、中、小三种类型的画笔来绘制12中不同的颜色,如果我们使用蜡笔,需要准备3*12=...

15330
来自专栏人工智能头条

在Apache Spark上跑Logistic Regression算法

22930
来自专栏企鹅号快讯

从图灵机开始

说到图灵机,我们首先要说说图灵这个人。笔者觉得我们这种搞计算机的人都应该知道并记得这个人。 图灵,1912年6月23日生于英国帕丁顿。是数学家、密码破译专家,当...

22680
来自专栏听雨堂

Pandas对行情数据的预处理

库里是过去抓取的行情数据,间隔6秒,每分钟8-10个数据不等,还有开盘前后的一些数据,用Pandas可以更加优雅地进行处理。 ? 需要把当前时间设置为index...

233100
来自专栏腾讯AlloyTeam的专栏

png的故事:获取图片信息和像素内容

现在时富媒体时代,图片的重要性对于数十亿互联网用户来说不言而喻,图片本身就是像素点阵的合集,但是为了如何更快更好的存储图片而诞生了各种各样的图片格式:jpeg、...

1.9K00
来自专栏牛客网

百度云部门 C++面试

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

17020
来自专栏图形学与OpenGL

机械版CG 实验1 像素点的生成

注:本博客实验教程的配套教材为《计算机图形学》(徐文鹏编)已由机械工业出版社于2009年2月出版。

10330
来自专栏CSDN技术头条

Hadoop旧mapreduce的map任务切分原理

前言 最近在工作过程中接触一些Hive数据仓库中的表,这些表实际是从关系型数据库通过Sqoop抽到Hive的。在开发过程中对map任务的划分进行性能调优,发现...

222100
来自专栏互联网大杂烩

String.hashcode 源码分析

接触编程这么久了,一直会遇到某些高频词,例如,哈希。hashtable,hashmap,hashset等等等。都有hash一次。那什么是哈希值呢?百度本科解释是...

10140

扫码关注云+社区

领取腾讯云代金券