Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- const int MAXN = 1001, INF = 1000;
- int n, k;
- int w[MAXN], v[MAXN];
- double tmp[MAXN];
- bool isGood(double x)
- {
- double sum = 0;
- for(int i = 0; i < n; i++)
- tmp[i] = v[i] - w[i] * x;
- sort(tmp, tmp + n, greater<double>());
- for(int i = 0; i < k; i++)
- sum += tmp[i];
- return (sum >= 0);
- }
- double getResult()
- {
- double L = 0, R = INF, mid;
- for(int i = 0; i < 50; i++)
- if(isGood(mid = (L + R) / 2)) L = mid;
- else R = mid;
- return L;
- }
- int main()
- {
- scanf("%d %d", &n, &k);
- for(int i = 0; i < n; i++)
- scanf("%d %d", &w[i], &v[i]);
- printf("%.2f\n",getResult());
- return 0;
- }
Add Comment
Please, Sign In to add comment