T188813 最小得分和

【问题描述】
给定一个长度为 N 的正整数序列，设数对(i，j)的得分 Sij=|ai-aj|，你需要找
出 K 对不同的数对，使得这 K 对数的得分之和最小，注意：不同数对可以重复
选择某个数，但选择的数对(i，j)中 i，j 不能相等，且(i，j)，(j，i)表示同
一个数对，也就是说只能选其中一个。

【输入描述】
第一行有两个正整数 N，K，如题所述。
接下来一行有 N 个正整数，表示序列中的数。

【输出描述】
只有一个数，表示最小的得分之和。

【输入样例】
5 5
5 3 1 4 2

【输出样例】
6

【样例解释】
以下括号里的数表示下标。
选择(1，4)，(2，4)，(2，5)，(3，5)这 4 对数，得分之和为 4。
再从(1，2)，(2，3)，(4，5)中任选 1 对，因为这 3 对的得分都一样,都为 2。

考虑将差值二分答案，首先将序列排序，在二分答案时如果当前有大于等于K对数满足小于当前的差值，则将区间向左移，否则向右移，在统计有多少对时维护一个j，0

细节：为了解决出现二分到pos时候答案个数超过k,但pos-1的时候却又小于k，可以直接统计pos-1时的对数，然后单独加上k-k'个差值为k的数对

#include 
using namespace std;
long long a[1000006];
long long ans,k;
long long n;
long long sum[1000009];
long long check(long long num){
    long long j=1;
    long long cnt=0;
    ans=0;
    for(long long i=1;i<=n;i++){
        while(j//在i的左端找到最先满足条件的位置
            j++;
        }
        cnt+=i-j; //有多少个可以与i构成满足条件
        if(i!=j)  ans+=a[i]*(i-j)-sum[i]+sum[j-1];
    }
    return cnt;
}
int main(){
    //freopen("mark.in","r",stdin);
    //freopen("mark.out","w",stdout);
    cin >> n >> k;
    for(long long i=1;i<=n;i++)
        cin >> a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+a[i];
    }
    long long mid;
    long long l=0;
    long long r=a[n]-a[1];
    long long maxder;
    while(l<=r){
        mid=(l+r)/2;
        if(check(mid)>=k){
            maxder=mid;
            r=mid-1;
        }
        else l=mid+1;
    }
    long long kk=check(maxder-1); //注意！这里记录的是当限制是k-1的情况！
    ans+=maxder*(k-kk); //统计刚好差值等于K的数
    cout << ans;
    system("pause");
    return 0;
}