鏈接

題意：

題解：

詳細解法看這里
這里說個點，eps一定要開足夠小，我一開始開的1e-5，結果就過了90%的數據，開到1e-7就足夠了

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } double eps=1e-7; const int maxn=1e5+9; double a[maxn],b[maxn]; double dis[maxn]; int n,k; bool check(double mid) {double ans=0;for(int i=1;i<=n;i++)dis[i]=a[i]-mid*b[i];sort(dis+1,dis+1+n,greater<double>());for(int i=1;i<=k;i++)ans+=dis[i];//for(int i=n;i>n-k;i--)ans+=dis[i];if(ans>eps)return 0;return 1; } int main() {cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];for(int i=1;i<=n;i++)cin>>b[i];double l=0,r=1000;while(r-l>eps){double mid=(l+r)/2;if(check(mid))r=mid;else l=mid;}printf("%.4f",l);return 0; }

[POJ2976]Dropping tests

這個題的話稍微改改代碼就OK了，這個題是選n-k個

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Loj #149. 01 分数规划（01分数规划模板题）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。