[ create a new paste ] login | about

Link: http://codepad.org/PdshCdHA    [ raw code | output | fork ]

nilukush - C++, pasted on May 12:
#include <iostream>
#include <deque>
#include <algorithm>

namespace
{
	typedef std::deque<int> array;
}

class number_max
{
	public :
		void operator()(std::deque<int>& n, int swaps)
		{
			// no elements in array
			if(n.empty()) return;
			
			nmax(n, swaps);
		}

	private :
		void nmax(std::deque<int>& n, int& swaps)
		{
			// Scan from beginning and get the maximum value in swaps number of elements, swap this value with the last unvisited digit
			for(size_t n_i(0), n_size(n.size()); (n_i < n_size) && (swaps > 0); ++n_i)
			{
				// get maximum value in the range [unvisited (n_i), element accessible by remaining number of swaps (n_i + swaps + 1) )
				size_t imax(get_max(n_i, n_i + swaps + 1, n));
				
				/*
				 * if the maximum index is same as the digit unvisited (n_i), then no need to swap as it is already in it's currect position. If not same, then we need to swap
				 * and reduce the number of remaining allowed swaps
				 */
				if(imax != n_i) { swap(n[imax], n[n_i]); swaps -= imax; }
			}
		}
		
		size_t get_max(size_t start, const size_t& end, const std::deque<int>& n)
		{
			size_t imax(start);
			for(size_t s(n.size()); (start < end) && (start < s); ++start)
			{ if(n[imax] < n[start]) imax = start; }

			return imax;
		}
		
		void swap(int& first, int& second)
		{
			first ^= second;
			second ^= first;
			first ^= second;
		}
};

int main()
{
	array a{2, 5, 1, 9, 3, 7, 2, 8, 9, 3};
	int swaps(5);
	number_max()(a, swaps);
	for(const int& e : a) std::cout << e;
	return 0;
}


Output:
1
2
3
In function 'int main()':
Line 57: error: a function-definition is not allowed here before '{' token
compilation terminated due to -Wfatal-errors.


Create a new paste based on this one


Comments: