题意描述
思路
对于最小值，我们发现如果两个数的差值小于等于2，那么两个数就可以合并在一起。 对于最大值，我们尽可能的让数字向空房子移动，如果移动后还有该数字存在，则尽可能的将数字向后移动。
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<long,long> PLL
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
const int N
=2*1e5+10;
const int M
=1e6+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
int a
[N
],f
[N
];
void solve(){
int n
;cin
>>n
;
map
<int,int> cnt
;
rep(i
,1,n
+1) cin
>>a
[i
],cnt
[a
[i
]]++;
sort(a
+1,a
+1+n
);
f
[1]=1;
int last
=a
[1];
rep(i
,2,n
+1){
if(a
[i
]-last
<=2){
f
[i
]=f
[i
-1];
}else{
f
[i
]=f
[i
-1]+1;
last
=a
[i
];
}
}
rep(i
,1,n
+1){
if(!cnt
[i
]) continue;
if(cnt
[i
-1]<=0){
cnt
[i
-1]++;
cnt
[i
]--;
}
if(cnt
[i
]>0){
cnt
[i
+1]++;
cnt
[i
]--;
}
}
int mx
=0;
for(auto c
: cnt
) if(c
.y
) mx
++;
cout
<<f
[n
]<<' '<<mx
<<endl
;
}
int main(){
IOS
;
solve();
return 0;
}
