题解 | #abc转换#

B题题解 从贪心的方面考虑,要求最小生成树,只需所有边的权值之和最小,也就是所有相邻两个点的差的绝对值的和最小,把输入的数从小到大排序,求差分数组的和即为最小权值.因为每两个相同的点对权值贡献为0,求出不重复的数保存到一个数组,再记录下每个重复的数的个数,可以发现开头和结尾对最长树链的贡献最多为2，中间的对总长不影响.一个点的话特别考虑且最多为三.

#include<bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define rep(i,k,n) for(int i=k;i<=n;i++)
#define _rep(i,n,k) for(int i=n;i>=k;i--)
#define N 200005
inline int read(){
    char c = getchar();int x = 0,s = 1;
    while(c < '0' || c > '9') {if(c == '-') s = -1;c = getchar();}
    while(c >= '0' && c <= '9') {x = x*10 + c -'0';c = getchar();}
    return x*s;
}
typedef unsigned long long ull;
typedef long long ll;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
int n;
ll res=0,ans=0;
ll a[N],c[N];
set<ll> se;
map<ll,ll> mp;
vector<ll> vec;
int main(){
	cin>>n;
	rep(i,1,n) {
		cin>>a[i];
        se.insert(a[i]);
        mp[a[i]] += 1;
		if(mp[a[i]] == 1) vec.push_back(a[i]);
	}
	sort(a+1,a+1+n);
	sort(vec.begin(),vec.end());
	ll k = se.size();
	rep(i,1,n) c[i] = a[i] - a[i-1];
	rep(i,2,n) res += abs(c[i]);
	if(k == 1){
		cout<<res<<" "<<min(n,3);
	}else{
		cout<<res<<" "<<(min(mp[vec[0]],2ll) + min(mp[vec[k-1]],2ll) + k - 2);
	}
	return 0;
}