my approach- I tried to solve it by just printing the kth largest number ,but getting segmentation fault. How to solve it? Please tell.
my code- OuMOD6 - Online C++0x Compiler & Debugging Tool - Ideone.com
You got the question wrong.
Consider
N = 1, K = 100
A=\{1000\}
This means that there are thousand weapons of type 1 and she can give each soldier 10 weapons of type 1, Thus ans = 10
For case
N = 2, K = 100
A=\{1000,1000\}
Here one answer can be to give first 50 soldier 20 weapons of type 1 and another 20 weapons each of type 2
As shown in example K can be greater than N thus, segmentation fault
Intended Solution
You can use binary search to check if she can give X weapons of the same type to all soldiers then to how many soldiers she can give to. If that answer is greater than $K$ then, look for the answer in the range X+1 to high
My code (Accepted)
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
ll n,k;
cin >> n >> k;
vector<int> arr(n);
for(auto &i:arr)cin >> i;
ll lo = 1;
ll ans = LLONG_MAX;
ll hi = *max_element(arr.begin(),arr.end());
while(lo <= hi){
ll mi = (lo+hi)/2;
ll cnt = 0;
for(auto &i: arr)cnt+=(i/mi);
if(cnt >= k){
lo = mi+1;
ans = mi;
}else hi = mi - 1;
}
if(ans == LLONG_MAX)ans = 0;
cout << ans;
return 0;
}
1 Like
Thankyou so much , it helped especially when you gave the intution behind it.