国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學(xué)院 > 開發(fā)設(shè)計(jì) > 正文

[POJ2976]Dropping tests（01分?jǐn)?shù)規(guī)劃）

2019-11-08 19:44:09
字體：大 中 小
供稿：網(wǎng)友

題目描述

傳送門 題意：給出ai,bi，選擇至少n-k個(gè)，使100*∑ai∑bi最大

題解

01分?jǐn)?shù)規(guī)劃裸題… 化一下式子R=∑ai∑bi，那么當(dāng)di=∑ai?R?∑bi>0的時(shí)候一定存在更優(yōu)解 二分R，算出di，貪心地選前n-k大，然后判斷是否存在更優(yōu)解就可以了

代碼

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>#include<cmath>using namespace std;#define N 1005const double eps=1e-4;int dcmp(double x){ if (x<=eps&&x>=-eps) return 0; return (x>0)?1:-1;}int n,k;double a[N],b[N],d[N],ans;bool check(double mid){ for (int i=1;i<=n;++i) d[i]=a[i]-mid*b[i]; sort(d+1,d+n+1); double now=0; for (int i=n;i>k;--i) now+=d[i]; return dcmp(now)>=0;}double find(){ double l=0.0,r=1.0,mid,ans; while (dcmp(r-l)>0) { mid=(l+r)/2.0; if (check(mid)) ans=l=mid; else r=mid; } return ans;}int main(){ while (~scanf("%d%d",&n,&k)) { if (!n&&!k) break; for (int i=1;i<=n;++i) scanf("%lf",&a[i]); for (int i=1;i<=n;++i) scanf("%lf",&b[i]); ans=100.0*find();

發(fā)表評(píng)論 共有條評(píng)論
用戶名: 密碼:
驗(yàn)證碼: 匿名發(fā)表
主站蜘蛛池模板： 海门市| 应用必备| 论坛| 古蔺县| 平度市| 北宁市| 富蕴县| 房产| 乐亭县| 衡东县| 甘肃省| 金乡县| 密云县| 凉城县| 泰宁县| 石首市| 海阳市| 龙游县| 乐都县| 湾仔区| 濮阳市| 汽车| 澄迈县| 济阳县| 乌鲁木齐市| 青川县| 东乌珠穆沁旗| 鄄城县| 庆阳市| 涡阳县| 剑河县| 吴桥县| 赞皇县| 苏尼特右旗| 北碚区| 磐安县| 韶关市| 遵化市| 张家界市| 江山市| 德安县|