Guest User

Untitled

a guest
Dec 13th, 2018
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdio.h>
  3. #include <vector>
  4. using namespace std;
  5. long long n, k, maxx = 0, ans = 0;
  6. vector<int> v;
  7. long long count(int mid) {
  8. long long ccnt = 0;
  9. for (int i = 0; i < v.size(); i++) {
  10. ccnt += v[i] / mid;
  11. //if (v[i] / mid == 0) return -1;
  12. }
  13. return ccnt;
  14. }
  15. void go(long long start, long long end) {
  16. if (start > end) return;
  17. long long mid = start - (start - end) / 2;
  18. long long cnt = count(mid);
  19. //printf("start = %lld mid = %lld end = %lld cnt = %lld\n", start, mid, end, cnt);
  20. //답 구하기 부분
  21. if (cnt >= n && mid > ans) { // ★★★ cnt==n하면 안 되고 cnt>=n 해줘야 한다 ★
  22. ans = mid;
  23. }
  24.  
  25. //재귀 부분
  26. if (cnt > n) {
  27. go(mid + 1, end);
  28. }
  29. else if (cnt < n) {
  30. go(start, mid - 1);
  31. }
  32. else { // cnt==n 일때도 계속 해줘야함
  33. go(mid + 1, end); // ★ go(mid,end)하게 되면 계속 같은 값으로 도는 현상 발생
  34. //go(mid+1,end);
  35. }
  36. }
  37. int main() {
  38. long long tmp;
  39. scanf("%lld %lld", &k, &n);
  40. for (int i = 0; i < k; i++) {
  41. scanf("%lld", &tmp);
  42. v.push_back(tmp);
  43. if (maxx < tmp) maxx = tmp;
  44. }
  45. go(1, maxx); // ★ go(0,maxx)하게 되면 0으로 나누는 값이 생겨서 런타임 에러 발생!
  46. printf("%lld\n", ans);
  47. return 0;
  48. }
Add Comment
Please, Sign In to add comment