Output the minimum number of balls Farmer John must initially pass to the cows, so that every cow can hold a ball at least once.


My 1st Correct Code

#include <iostream>
#include <algorithm>
#define INF 1001
int main() {
	int N;
	std::cin >> N;

	int* x = new int[N+2];
	for (int i = 0; i < N; i++) {
		std::cin >> x[i];
	}
	std::sort(x, x + N);

	int next[101];
	next[0] = 1; next[N - 1] = N - 2;
	for (int i = 1; i < N-1; i++) {
		next[i] = (x[i]-x[i - 1] <= x[i+1] - x[i]) ? i - 1 : i + 1;
	}

	int passed[101] = { 0, };
	for (int i = 0; i < N; i++) {
		passed[next[i]]++;
	}

	int ball = 0;
	for (int i = 0; i < N; i++)
	{
		if (!passed[i])
			ball++;
		if (i < next[i] && next[next[i]] == i && passed[i] == 1 && passed[next[i]] == 1)
			ball++;
	}
	std::cout << ball << "\n";
}


comments

2020-01-17 couldn’t understand it for a long time