01规划的模板题 - 好文

链接：https://www.nowcoder.com/acm/contest/143/A
<https://www.nowcoder.com/acm/contest/143/A>
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

Kanade selected n courses in the university. The academic credit of the i-th
course is s[i] and the score of the i-th course is c[i].

At the university where she attended, the final score of her is

Now she can delete at most k courses and she want to know what the highest
final score that can get.

输入描述:
The first line has two positive integers n,k The second line has n positive
integers s[i] The third line has n positive integers c[i]
输出描述:
Output the highest final score, your answer is correct if and only if the
absolute error with the standard answer is no more than 10-5

示例1

输入
3 1 1 2 3 3 2 1
输出
2.33333333333
说明
Delete the third course and the final score is
备注:
1≤ n≤ 105 0≤ k < n 1≤ s[i],c[i] ≤ 103
题意：显而易见，这道题用到了01规划，通俗点讲就是有n种物品，每个物品都有a[i],b[i]两种不同的情况，选择n-k个元素要求

最大，反观这道题，直接将数据带入即可

我是使用的01规划中的二分法写的，但是这道题有一点要改进的就是至多删除k个元素，表示可以删除<=k个元素然后取最大值

这是我看的关于01规划算法的介绍https://blog.csdn.net/hzoi_ztx/article/details/54898323
<https://blog.csdn.net/hzoi_ztx/article/details/54898323>

主要公式：求max{f(r)}

#include <iostream>//二分法 #include <stdio.h> #include <algorithm> using
namespace std; int n,k,a[100005],b[100005]; double ps[100005]; const double
eps=1e-5; bool ok(double
h)//f(r)=xi*a[i]*b[i]的和-xi*a[i]的和*r=(a[i]*b[i]的和-a[i]的和*r)*xi;为求最大值将xi全部为1，之后再将要删去的定为0.（xi={0,1}）
{ for(int i=1;i<=n;i++)
ps[i]=a[i]*b[i]-h*a[i];//ps数组表示横坐标为h是纵坐标的值后再将其全部加起来得到ans sort(ps+1,ps+1+n);
double ans=0;
//ans表示max{f(r)}即垂直于x轴坐标为h的直线与ps所代表的直线方程的交点；如果ans大于0则表示最大值在右边，否则在左边 for(int
i=n;i>=k+1;i--) ans+=ps[i]; for(int i=2;i<=k;i++) if(ps[i]>0)ans+=ps[i]; return
ans>-eps; } void sol() { for(int i=1;i<=n;i++) scanf("%d",a+i); for(int
i=1;i<=n;i++) scanf("%d",b+i); double l=0,r=10000; while(r-l>eps) { double
mid=(l+r)/2; if(ok(mid)) l=mid; else r=mid; } printf("%.11lf\n",l); } int
main() { scanf("%d%d",&n,&k); sol(); }

热门工具换一换