goat.cpp

#include <iostream>
using namespace std;
void InsertionSort(unsigned* arr, int n)
{
	int i, j, key;
	for (i = 1; i < n; i++)
	{
		j = i - 1;
		key = arr[i];
		while (j >= 0 && key > arr[j])
		{
			arr[j + 1] = arr[j];
			j = j - 1;
		}
		arr[j + 1] = key;
	}
}
int returnFirstUnsent(bool* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		if (arr[i] == 0)
			return i;
	}
}
int main()
{
	unsigned n = 0, k = 0;
	cout << "Enter number of goat N and then K courses: " << endl;
	cin >> n >> k;
	unsigned* weights = new(nothrow) unsigned[n];
	if (!weights)
	{
		cout << "Error allocating memory..." << endl;
		return -1;
	}
	cout << "Enter weight of every goat respectively: " << endl;
	for (int i = 0; i < n; i++)
	{
		cout << "Goat[" << i + 1 << "] : " << endl;
		cin >> weights[i];
	}
	InsertionSort(weights, n);

	bool* sentSheep = new(nothrow) bool[n];
	
	if (!sentSheep)
	{
		cout << "Error allocating memory..." << endl;
		return -1;
	}
	
	for (int i = 0; i < n; i++)
		sentSheep[i] = 0;

	int minC = 1186;
	int tempCourses = k; 
	int curr = 0;
	int i = 0, j = 0;
	bool firstCheck = true;
	while (tempCourses > 0)
	{
		i = returnFirstUnsent(sentSheep,n);
		tempCourses--;
		firstCheck = true;
		while (i < n) 
		{
			int temp = curr;
			if (!sentSheep[i] && !firstCheck)
				curr += weights[i];
			if (!sentSheep[i] && firstCheck)
			{
				curr = weights[i];
				firstCheck = false;
			}
			if (curr <= minC)
			{
				sentSheep[i] = 1;
			}
			if (curr > minC)
			{
				curr = temp;
			}
			i++;
		}
	}
	


	delete[] weights;
	delete[] sentSheep;
	system("PAUSE");
}