Guest User

Untitled

a guest
Jan 4th, 2018
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.22 KB | None | 0 0
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<vector>
  4.  
  5. using namespace std;
  6.  
  7. long long binSearch(long long* arr, long long N, long long K);
  8. bool possible(long long middle, long long *arr, long long N, long long K);
  9.  
  10. vector<long long> v;
  11. int main() {
  12. int N, K;
  13. cin >> N >> K;
  14.  
  15. long long * arr = new long long[K];
  16. long long sum = 0;
  17. for (int i = 0; i < K; i++)
  18. cin >> arr[i];
  19.  
  20. cout << binSearch(arr, N, K) << endl;
  21. for (int z : v) {
  22. cout << z + 1 << endl;
  23. }
  24. system("pause");
  25. return 0;
  26. }
  27.  
  28. long long binSearch(long long * arr, long long N, long long K)
  29. {
  30. long long left = 0;
  31. long long right = N + 1;
  32. while (left != right - 1) {
  33. long long middle = (left + right) / 2;
  34. if (possible(middle, arr, N, K))
  35. left = middle;
  36. else
  37. right = middle;
  38. }
  39. if (left == right)
  40. return 0;
  41. return left;
  42. }
  43.  
  44. bool possible(long long middle, long long * arr, long long N, long long K)
  45. {
  46. if (middle == 0)
  47. return false;
  48. long long k = 0;
  49.  
  50. for (long long i = 0; i < K; i++)
  51.  
  52. k += (arr[i] / middle);
  53.  
  54. if (k >= N)
  55. {
  56. v.clear();
  57. for (long long i = 0; i < K; i++)
  58. {
  59. for (long long j = 0; j < arr[i] / middle; j++)
  60. v.push_back(i);
  61. }
  62. }
  63. return (k >= N) ? true : false;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment