Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <stdio.h>
- using namespace std;
- vector<unsigned int> a;
- vector<unsigned int> b;
- double last_success_x;
- vector<pair<double, unsigned int> > rest;
- double diff;
- bool sortinrev(const pair<double, unsigned int> &a, const pair<double, unsigned int> &b)
- {
- return (a.first > b.first);
- }
- bool iteration(unsigned int n, unsigned int k, double x)
- {
- unsigned int i;
- for (i = 0; i < n; ++i)
- {
- rest[i] = make_pair(a[i] - b[i] * x, i);
- }
- sort(rest.begin(), rest.end(), sortinrev);
- double sum = 0.;
- for (i = 0; i < k; ++i)
- {
- sum += rest[i].first;
- }
- return sum >= 0;
- }
- void solve(unsigned int n, unsigned int k, double r_lim)
- {
- double left = last_success_x = 0.;
- double right = r_lim;
- double x = (left + right) / 2;
- unsigned int i;
- rest = vector<pair<double, unsigned int> >(n);
- while (right - left >= diff)
- {
- // cout << "right = " << right << " left = " << left << endl;
- if (iteration(n, k, x))
- {
- left = last_success_x = x;
- }
- else
- {
- right = x;
- }
- x = (left + right) / 2;
- }
- // cout << "last_success_x = " << last_success_x << endl;
- iteration(n, k, last_success_x);
- for (i = 0; i < k; ++i)
- {
- printf("%d ", rest[i].second + 1);
- //cout << rest[i].second + 1 << " ";
- }
- printf("\n");
- // cout << endl;
- }
- int main()
- {
- unsigned int requests_num;
- unsigned int n, k;
- unsigned int i, j;
- unsigned int temp;
- double max_a, min_b, max_b;
- scanf("%u", &requests_num);
- for (i = 0; i < requests_num; ++i)
- {
- scanf("%u %u", &n, &k);
- max_a = 0;
- min_b = 1000001;
- max_b = 0;
- a = vector<unsigned int>(n);
- b = vector<unsigned int>(n);
- for (j = 0; j < n; ++j)
- {
- scanf("%u", &temp);
- max_a = temp > max_a ? temp : max_a;
- a[j] = temp;
- }
- for (j = 0; j < n; ++j)
- {
- scanf("%u", &temp);
- max_b = temp > max_b ? temp : max_b;
- min_b = temp < min_b ? temp : min_b;
- b[j] = temp;
- }
- // cout << "max_a = " << max_a << endl;
- diff = 2. / UINT32_MAX;
- //cout << max_a << " " << min_b << " " << max_b << endl;
- solve(n, k, max_a / min_b);
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment