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_silver_feb19/2.in", "r", stdin);
- freopen("herding.out", "w", stdout);
- int n;
- cin >> n;
- int pos[n];
- for(int i=0; i<n; i++){
- cin >> pos[i];
- }
- sort(pos, pos+n);
- int minsize = 0;
- //cout << "n => " << n << endl;
- //for (int i = 0; i < n; i++)
- //{
- //cout << "i: " << pos[i] << endl;
- //}
- if(pos[n-1]- pos[1] == n-2 && pos[1] - pos[0] > 2){
- //exception will apply only gap > 2 since 2 eg.12346 will cause only one move
- minsize = 2;
- }else if(pos[n-2]-pos[0] == n-2 && pos[n-1] - pos[n-2] > 2){
- //exception will apply only gap > 2 since 2 eg.12346 will cause only one move
- minsize = 2;
- }else{
- int j = 1, best = 0;
- for (int i = 0; i < n ; i++)
- {
- while (j < n )
- {
- int cover = j- i + 1;
- int gap = (pos[j] - pos[i] + 1) - cover;
- int remain = n - cover ;
- //cout << "i: " << i << ", j: " << j << ", val[i]: " << pos[i] << ", val[j]: " << pos[j] << ", gap: " << gap << " , remain. " << remain << endl;
- if (gap > remain)
- {
- break;
- }
- best = max(best, cover);
- //cout << "To best: " << j - i + 1 << " => " << best << endl;
- j++;
- }
- }
- minsize = n - best;
- }
- cout << minsize << '\n';
- int maxval = max(pos[n-1]-pos[1], pos[n-2]-pos[0]) - (n - 2);
- cout << maxval << '\n';
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
