题目链接
题目思路
01分数规划入手题,千万不要把value和weight看反!
代码实现
#include<bits/stdc++.h> using namespace std; #define ll long long const int Max=1e5+5; int a[Max],b[Max]; int n,k; double p[Max]; bool cmp(double aaa,double bbb) { return aaa>bbb; } bool check(double x) { double res=0; for(int i=1;i<=n;i++) p[i]=b[i]-x*a[i]; sort(p+1,p+1+n,cmp); for(int i=1;i<=k;i++) res+=p[i]; return res>=0; } int main() { int t; cin>>t; while(t--) { cin>>n>>k; for(int i=1;i<=n;i++) cin>>a[i]>>b[i]; double l=0,r=1e9; double ans; while(r-l>=1e-6) { double mid=(l+r)/2; if(check(mid)) { ans=l; l=mid; } else r=mid; } cout<<fixed<<setprecision(2)<<ans<<endl; } return 0; }