Maximize the profit after selling the tickets | Set 2 ( For elements in range [ 1 , 10 ^ 6 ] ) | Function to find maximum profit after selling K tickets ; Frequency array to store freq of every element of the array ; Modify the arr [ ] so that the array is sorted in O ( N ) ; Variable to store answer ; Traverse the array while K > 0 and j >= 0 ; If arr [ i ] > arr [ j ] then ticket can be brought from counter [ j + 1 , N ] ; If arr [ j ] = = arr [ i ] decrement j until arr [ j ] != arr [ i ] ; Sell tickets from counter [ j + 1 , N ] ; All elements of array are equal Send tickets from each counter 1 time until K > 0. ; Converting answer from long long to int ; Driver Code ; Given Input ; Function Call
def maxAmount ( n , k , arr ) : NEW_LINE INDENT A = [ 0 for i in range ( 1000001 ) ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT A [ arr [ i ] ] += 1 NEW_LINE DEDENT j = 0 NEW_LINE for j in range ( 1000001 ) : NEW_LINE INDENT while ( A [ i ] != 0 ) : NEW_LINE INDENT arr [ j ] = i ; NEW_LINE j += 1 NEW_LINE A [ i ] -= 1 NEW_LINE DEDENT DEDENT ans = 6 NEW_LINE mod = 1000000007 NEW_LINE i = n - 1 NEW_LINE j = n - 2 NEW_LINE while ( k > 0 and j >= 0 ) : NEW_LINE INDENT if ( arr [ i ] > arr [ j ] ) : NEW_LINE INDENT ans = ans + min ( k , ( i - j ) ) * arr [ i ] NEW_LINE k = k - ( i - j ) NEW_LINE arr [ i ] -= 1 NEW_LINE DEDENT else : NEW_LINE INDENT while ( j >= 0 and arr [ j ] == arr [ i ] ) : NEW_LINE INDENT j -= 1 NEW_LINE DEDENT if ( j < 0 ) : NEW_LINE INDENT break NEW_LINE DEDENT ans = ans + min ( k , ( i - j ) ) * arr [ i ] NEW_LINE k = k - ( i - j ) NEW_LINE arr [ i ] -= 1 NEW_LINE DEDENT DEDENT while ( k > 0 and arr [ i ] != 0 ) : NEW_LINE INDENT ans = ans + min ( n , k ) * arr [ i ] NEW_LINE k -= n NEW_LINE arr [ i ] -= 1 NEW_LINE DEDENT ans = ans % mod NEW_LINE x = ans NEW_LINE return x NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 5 NEW_LINE k = 3 NEW_LINE arr = [ 4 , 3 , 6 , 2 , 4 ] NEW_LINE ans = maxAmount ( n , k , arr ) NEW_LINE print ( ans ) NEW_LINE DEDENT