首页 > 其他 > 详细

联赛练习:draw

时间:2018-07-13 00:59:40      阅读:68      评论:0      收藏:0      [点我收藏+]

标签:splay   价格   蛋疼   它的   01分数规划   ble   esp   color   pre   

 

【题目描述】

有一天, WJK不小心透露出了他会算命的秘密,大家纷纷前往拜访,于是WJK拿出私藏的小木箱,给大家露两手。(结果是要收钱的!)

小木箱里装有N张牌,每张牌分别有一个价格vi和人品值ri,现在要求从中选出K张牌,使得单位人品值最大。(单位人品值=总人品值之和/总价格之和)

 

【输入】

第1行:两个整数N和K(1<=K<=N<=10^5) .

第二至N+1行为每张牌的价格vi和人品值ri。(1<=vi,ri<=10^7)

 

【输出】

第1行:单位人品的最大值(精确到小数点后两位).

【输入样例】

3 2
2 2
5 3
2 1

【输出样例】

0.75

【提示】

选1号和3号牌,单位人品值为(2+1)/(2+2)=0.75

 题解:

01分数规划

设:

$$\sum_{i=1}^n \frac{r_ix_i}{v_ix_i}>=p$$

其中x为1或0,即选或不选

现在考虑最大化p,显然,p具有单调性,所以可以二分p

那么如何验证呢?

整理上式,有

$$\sum_{i=1}^nr_ix_i=\sum_{i=1}^npv_ix_i$$

移项,得:

$$\sum_{i=1}^nx_i(r_i-pv_i)>=0$$

因此,对于p,我们可以先算出每一个r-k*p,接着,取前k大的值求和(相当于前k大的x取1,其余取0),若其和>=0,则证明此时的p合法

另外二分小数这东西略蛋疼......实际上你只需要限制它的二分次数为55次即可

代码如下:

 

技术分享图片
#include<bits/stdc++.h>
using namespace std;
int n,k;
int v[100005],r[100005];
double ans;
bool cmp(double a,double b)
{
    return a>b;
}
bool check(double p)
{
    double sum=0.00;
    double rt[100005];
    for(int i=1;i<=n;i++)
        rt[i]=(double)r[i]-p*(double)v[i];
    sort(rt+1,rt+1+n,cmp);
    for(int i=1;i<=k;i++)
        sum+=rt[i];
    if(sum>=0.00)
       return true;
    else
       return false;          
}
int main()
{
    double t=-1.00;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
        {
            scanf("%d%d",&v[i],&r[i]);
            t=(double)r[i]/v[i]>t?(double)r[i]/v[i]:t;
        }
    int tot=0;        
    double L=0.01,R=t;
    while(tot<=55)
          {
                 tot++;
                 double mid=(L+R)/2;
                 if(check(mid))
                    {
                          ans=mid;
                          L=mid+0.01;
                    }
                 else
                   R=mid-0.01;   
          }
    printf("%.2lf",ans);                          
    return 0;
}
View Code

 

联赛练习:draw

标签:splay   价格   蛋疼   它的   01分数规划   ble   esp   color   pre   

原文:https://www.cnblogs.com/nanjolno/p/9302485.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号