/* There are N numbers in array. K iterations have to be performed on the array elements. In each iteration, largest element Ai of the array is chosen and added to the answer and removed from array. At the same time Ai/2 is inserted back to array input First line contains 2 integers N followed by K. Next line contains N space separated integers input 2 4 8 9 output 25 Explanation At first iteration max value is 9 (8, 9) At second iteration max value is 8 (8, 4) At third iteration max value is 4 (4, 4) At fourth iteration max value is 4 (4, 2) So answer : 9 + 8 + 4 + 4 = 25 */ #include #include #include #include using namespace std; //vector approach int main() { //N and K from user int a; int n,k; cin >> n >> k; long long ans = 0; int cnt = 1; //input from user for array vector input(n); for(int i=0;i> a; input[i] = a; } while(cnt<=k) { sort(input.begin(),input.end()); int val = input[n-1]; ans += val; input[n-1] = val/2; ++cnt; } cout << ans << endl; return 0; } //multiset approach int main_1() { //N and K from user int a; int n,k; cin >> n >> k; long long ans = 0; int cnt = 1; //input from user for array multiset> input; for(int i=0;i> a; input.insert(a); } while(cnt<=k) { auto itr = prev(input.end()); int val = *itr; ans += val; input.insert(val/2); input.erase(itr); ++cnt; } cout << ans << endl; return 0; }

VectorVsMultimap