题意：给你n个数，让你选出k个，让这k个两两差的和最小。输出k个数的下标。（n<=3e5）
思路：
我们可以知道要选的k个肯定是排序后连续的k个。
所以我们可以O(n)以长度为k的尺子从头推到尾，但关键是每次向右挪一位，这个区间的两两差值和的变化怎么求。
首先得计算区间[1-k]的差值和，怎么计算?可以利用前缀和（sum数组）, [1 - i] 推到 [1 - i+1] ，那么多加的差值就是a[i+1]*i - sum[i] , 这样就可以O(k)复杂度推出区间[1-k].
其次是要向右平移这个k区间, a[i] - a[i+k-1] 推到 a[i+1] - a[i+k], 就会加上a[i+k]与中间那段（a[i+1]-a[i+k-1]）的差值和， 同样利用前缀和可以快速计算出是a[i+k]*(k-1) - (sum[i+k-1]-sum[i]). 同时也要减去a[i]与中间那段（a[i+1]-a[i+k-1]）的差值和, 同样可以得到是(sum[i+k-1]-sum[i])-a[i]*(k-1).
这样跑一次维护一下最小值就行了。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 3e5+5; struct node { ll v; int id; bool operator < (const node &a) const { if(v == a.v) return id < a.id; else return v < a.v; } }a[maxn]; ll sum[maxn]; int main(void) { int n, k; while(cin >> n) { memset(sum, 0, sizeof(sum)); for(int i = 1; i <= n; i++) scanf("%I64d", &a[i].v), a[i].id = i; scanf("%d", &k); sort(a+1, a+1+n); for(int i = 1; i <= n; i++) sum[i] = sum[i-1]+a[i].v; ll ans; ll pre = 0; for(int i = 1; i <= k; i++) pre += a[i].v*(i-1)-sum[i-1]; ans = pre; int index = 1; for(int i = k+1; i <= n; i++) { pre += a[i].v*(k-1)-(sum[i-1]-sum[i-k]); pre -= (sum[i-1]-sum[i-k])-a[i-k].v*(k-1); if(pre < ans) { ans = pre; index = i-k+1; } } for(int i = index; i < index+k; i++) printf("%d ", a[i].id); puts(""); } return 0; }