01分数规划

mac2025-10-23  5

#include <iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; vector<double> num; const double eps = 1e-6; double a[1015],b[1015]; int n,k; bool judge(double mid) { num.clear(); for (int i = 0; i < n; i++) { num.push_back(a[i]-b[i]*mid); } sort(num.begin(),num.end()); double res = 0; for (int i = k; i < n; i++) { res += num[i]; } if( res > 0 ) return true; else return false; } int main() { while( cin >> n >> k ) { if( n == 0 && k == 0 ) break; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; double l = 0, r = 1e18; double ans = 0; while( r - l > eps ) { double mid = ( r + l ) / 2; if( judge(mid) ) { ans = mid; l = mid; }else r = mid; } ans *= 100; int res = floor(ans+0.5); cout << res << endl; } return 0; }
最新回复(0)