Skip to content

Instantly share code, notes, and snippets.

@vectorman1 vectorman1/goats.cpp
Created Jul 11, 2016

Embed
What would you like to do?
Kozichki :)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> sheep;
bool cr(const int a, const int b)
{
return a > b;
}
int getTravels(int size)
{
vector<int> boats;
int i, j;
for( i = 0; i < sheep.size(); i++ )
{
for( j=0; j < boats.size(); j++ )
{
if( boats[j] + sheep[i] <= size)
{
boats[j] += sheep[i];
break;
}
}
if( j == boats.size() )
{
boats.push_back(sheep[i]);
}
}
return boats.size();
}
int up, down, middle, res;
int n, i, k;
int main()
{
scanf("%d %d", &n, &k);
sheep.resize(n);
for(i=0;i<n;i++)
{
scanf("%d", &sheep[i]);
up += sheep[i];
}
sort(sheep.begin(), sheep.end(), cr);
down = sheep[0];
while( up > down )
{
middle = (up+down) / 2;
res = getTravels(middle);
if( res > k )
{
down = middle+1;
}
else
{
up = middle-1;
}
}
middle = (up+down) / 2;
if( getTravels(middle) > k ) middle++;
printf("%d\n", middle);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.