Order of indices which is lexicographically smallest and sum of elements is <= X | C ++ implementation of the approach ; Function to return the chosen indices ; Maximum indices chosen ; Try to replace the first element in ans by i , making the order lexicographically smaller ; If no further replacement possible return ; If found an index smaller than ind and sum not exceeding X then remove index of smallest value from ans and then add index i to ans ; Driver code ; Print the chosen indices
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > solve ( int X , vector < int > & A ) { int min = INT_MAX ; int ind = -1 ; for ( int i = 0 ; i < A . size ( ) ; i ++ ) { if ( A [ i ] < min ) { min = A [ i ] ; ind = i ; } } int maxIndChosen = X / min ; vector < int > ans ; if ( maxIndChosen == 0 ) { return ans ; } for ( int i = 0 ; i < maxIndChosen ; i ++ ) { ans . push_back ( ind ) ; } int temp = maxIndChosen ; int sum = maxIndChosen * A [ ind ] ; for ( int i = 0 ; i < ind ; i ++ ) { if ( sum - X == 0 temp == 0 ) break ; while ( ( sum - A [ ind ] + A [ i ] ) <= X && temp != 0 ) { ans . erase ( ans . begin ( ) ) ; ans . push_back ( i ) ; temp -- ; sum += ( A [ i ] - A [ ind ] ) ; } } sort ( ans . begin ( ) , ans . end ( ) ) ; return ans ; } int main ( ) { vector < int > A = { 5 , 6 , 4 , 8 } ; int X = 18 ; vector < int > ans = solve ( X , A ) ; for ( int i = 0 ; i < ans . size ( ) ; i ++ ) cout << ans [ i ] << " ▁ " ; return 0 ; }