P1090 为什么 90

#include<bits/stdc++.h>
#define ll long long
#define un unsigned
#define int long long
#define db double
#define inf 1000000000000000
#define st string
#define ct const
#define xh(a,b,c) for(int a=b;a<=c;a++)
#define wx while(1)
#define dn(a,b,c) for(int a=b;a>=c;a--)
using namespace std;
vector<int>v;
int n;
int x;
int a[100001]; 
int ans;
void check(int k){
	int l=0,r=v.size()-1;
	int t=r;
	int minn=INT_MAX;
	while(l<=r){
		int mid=(l+r)/2;
		if(v[mid]>=k){
			if(v[mid]-k<minn||v[mid]-k==minn&&mid<t){
				minn=v[mid]-k;t=mid;
			}
		}
		if(v[mid]>=k)r=mid-1;
		else l=mid+1;
	}
	v.insert(v.begin()+t+1,k);
}
signed main(){
	cin>>n;
	xh(i,1,n){
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	xh(i,1,n)v.push_back(a[i]);
	while(1){
		if(v.size()==1){
			cout<<ans;
			return 0;
		}
		int t=v[0]+v[1];
		ans+=t;
		v.erase(v.begin()+0);
		v.erase(v.begin()+0);
		
		check(t);
	}
	return 0;
}