ri，被黄题虐。
思路：贪心？？
提交：2次
错因：没有特判
题解：
先排序。
最小代价：固定区间长度为(n),我们扫一遍数组看区间最多包含几个数，设为 (mx) ，答案就是(n-mx+1)；然而还要特判一种，见下。
此时答案是2，但是我们会算成1
最大代价：考虑一定是往一边缩的感觉，于是是端点先跳到一边的里面，然后这一边开始往里缩，直到缩成n
所以答案是(max(a[n-1]-a[1]+1,a[n]-a[2]+1)-(n-1)+1),最后的加一是刚开始端点往里跳的代价。
代码：
#include<bits/stdc++.h>
#define R register int
using namespace std;
namespace Luitaryi {
inline int g() { R x=0,f=1;
register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*f;
} const int N=100010;
int n,mx,mn,a[N];
inline void main() {
mn=n=g(); for(R i=1;i<=n;++i) a[i]=g();
sort(a+1,a+n+1);
if((a[n-1]-a[1]+1==n-1&&a[n]-a[n-1]+1>3)||(a[n]-a[2]+1==n-1&&a[2]-a[1]+1>3)) mn=2;
else {
R p=1;
for(R i=1;i<=n;++i) {
while(p<n&&a[p+1]-a[i]+1<=n) ++p;
mn=min(mn,n-(p-i+1));
}
} printf("%d
%d
",mn,max(a[n-1]-a[1],a[n]-a[2])-n+2);
}
} signed main() {Luitaryi::main(); return 0;}
2019.10.18
28