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
