从n根筷子里面， 选择k+8个集合的筷子，每个集合三根筷子， A<=B<=C, 费用是(A-B)^2,
问最小的费用是多少。
将n根筷子排序之后，可以知道A和B的下标一定是连续的。
比如有 A B C D , 那么不可能是A C 一个集合， B D一个集合， 因为这样费用反而更大。
设dp[i][j] 为第i个集合的筷子，以j结尾， 就是说 A和B分别是第j和第j-1个筷子
dp[i][j] = min(dp[i-1][k]) + (a[j]-a[j-1])^2
那么如何处理第三根筷子呢？
只要将筷子从大到小排序。
dp[i][j] 的j是从3*i开始的，
而dp[i-1][k]的k是从(i-1)*3开始的，这样就保证了每个集合在前面的筷子中，都有一根筷子与自己配对。
dp[i][j] = min(dp[i-1][k]) + (a[j]-a[j-1])^2 这个循环可以用单调递增队列来优化，保证队头最小就行了。
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
#include <unordered_map>
typedef __int64 LL;
const int INF = ; /*
A B 绝逼是连续的，问题是C怎么怎么描述
dp[i][j] 第i套筷子是由j结束 dp[i][j] = min(dp[i][j],dp[i-1][k])
*/ const int N = + ;
int a[N];
int dp[][N];
int q[N], head, tail;
int main()
{
int t, n, k;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &k, &n);
k += ;
for (int i = ;i <= n;++i)
scanf("%d", &a[i]);
std::sort(a + , a + n + ,std::greater<int>());
for (int i = ;i <= k;++i)
{
head = tail = ;
for (int j = (i-)*;j <= * i - ;++j)
{
while (head < tail && dp[i - ][q[tail - ]] >= dp[i - ][j])
tail--;
q[tail++] = j;
}
for (int j = * i; j <= n;++j)
{
dp[i][j] = (a[j] - a[j - ])*(a[j] - a[j - ]) + dp[i - ][q[head]];
while (head < tail && dp[i - ][q[tail - ]] >= dp[i - ][j-])
tail--;
q[tail++] = j - ;
}
}
int ans = INF;
for (int j = * k;j <= n;++j)
ans = std::min(ans, dp[k][j]);
printf("%d\n", ans); }
return ;
}