Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<algorithm>
- #include<vector>
- using namespace std;
- long long binSearch(long long* arr, long long N, long long K);
- bool possible(long long middle, long long *arr, long long N, long long K);
- vector<long long> v;
- int main() {
- int N, K;
- cin >> N >> K;
- long long * arr = new long long[K];
- long long sum = 0;
- for (int i = 0; i < K; i++)
- cin >> arr[i];
- cout << binSearch(arr, N, K) << endl;
- for (int z : v) {
- cout << z + 1 << endl;
- }
- system("pause");
- return 0;
- }
- long long binSearch(long long * arr, long long N, long long K)
- {
- long long left = 0;
- long long right = N + 1;
- while (left != right - 1) {
- long long middle = (left + right) / 2;
- if (possible(middle, arr, N, K))
- left = middle;
- else
- right = middle;
- }
- if (left == right)
- return 0;
- return left;
- }
- bool possible(long long middle, long long * arr, long long N, long long K)
- {
- if (middle == 0)
- return false;
- long long k = 0;
- for (long long i = 0; i < K; i++)
- k += (arr[i] / middle);
- if (k >= N)
- {
- v.clear();
- for (long long i = 0; i < K; i++)
- {
- for (long long j = 0; j < arr[i] / middle; j++)
- v.push_back(i);
- }
- }
- return (k >= N) ? true : false;
- }
Advertisement
Add Comment
Please, Sign In to add comment