Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- string info(vector<int> &herd, int &curr_cow, int &farthest_cow){
- string info = ", curr_cow: " + to_string(curr_cow) +"#H:"+to_string(herd[curr_cow])
- + ", farthest_cow: "+to_string(farthest_cow)+"#H: "+to_string(herd[farthest_cow]);
- return info;
- }
- int main() {
- freopen("herding.in", "r", stdin);
- int n;
- cin >> n;
- vector<int> herd(n);
- for (int i = 0; i < n; ++i) {
- cin >> herd[i];
- }
- sort(herd.begin(), herd.end());
- int min_moves = INT32_MAX;
- if (herd[n - 2] - herd[0] == n - 2 && herd[n - 1] - herd[n - 2] > 2) {
- min_moves = 2;
- cout << "min_moves#1" << endl;
- } else if (herd[n - 1] - herd[1] == n - 2 && herd[1] - herd[0] > 2) {
- min_moves = 2;
- cout << "min_moves#2" << endl;
- } else {
- // min is the patch of length n that has the least # of gaps
- int farthest_cow = 0;
- for (int curr_cow = 0; curr_cow < n; ++curr_cow) {
- cout << "[for] " +info(herd, curr_cow, farthest_cow) << endl;
- while (
- farthest_cow + 1 < n
- && herd[farthest_cow + 1] - herd[curr_cow] < n
- ) {
- farthest_cow++;
- cout << "[while] " +info(herd, curr_cow, farthest_cow) << endl;
- }
- min_moves = min(min_moves, n - (farthest_cow - curr_cow + 1));
- cout << "min_moves: "+to_string(min_moves) << endl;
- }
- }
- // calculate the number of empty cells
- int gap_num = 0;
- for (int i = 1; i < n; i++) {
- gap_num += herd[i] - herd[i - 1] - 1;
- }
- // max is the maximum of the total gap minus either the first or last gap
- int max_moves = max(
- gap_num - (herd[1] - herd[0] - 1),
- gap_num - (herd[n - 1] - herd[n - 2] - 1)
- );
- freopen("herding.out", "w", stdout);
- cout << min_moves << '\n' << max_moves << endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement