Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main(){
- ios_base::sync_with_stdio(0), cin.tie(0);
- freopen("herding.in", "r", stdin);
- freopen("herding.out", "w", stdout);
- int n;
- cin >> n;
- // cout << n << '\n';
- int pos[n];
- for(int i=0; i<n; i++){
- cin >> pos[i];
- }
- sort(pos, pos+n);
- int minsize = 0;
- if(pos[n-1]- pos[1] == n-2 && pos[1] - pos[0] > 2){
- minsize = 2;
- }else if(pos[n-2]-pos[0] == n-2 && pos[n-1] - pos[n-2] > 2){
- minsize = 2;
- }else{
- int j = 0, best = 0;
- for (int i = 0; i < n ; i++)
- {
- while (j < n -1 )
- {
- //cout << "i: " << i << ", j: " << j << ", val[i]: " << pos[i] << ", val[j+1]: " << pos[j+1] << ", diff: " << pos[j+1] - pos[i] << " vs. " << n-1 << endl;
- if (pos[j+1] - pos[i] <= n-1)
- {
- j++;
- }else
- {
- break;
- }
- best = max(best, j - i + 1);
- //cout << "To best: " << j - i + 1 << " => " << best << endl;
- }
- }
- minsize = n - best;
- }
- cout << minsize << '\n';
- int maxval = max(pos[n-1]-pos[1], pos[n-2]-pos[0]) - (n - 2);
- cout << maxval << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
