Build Pylons
链接：https://ac.nowcoder.com/acm/contest/303/E
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
星际争霸(StarCraft)中，每个种族都有各自的基础单位，人族是宇宙建设车(SCV)，异虫是工蜂(Drone)，星灵是探机普罗比斯(Probe)，他们会建造建筑和采集资源，俗称农民。
SCV在开始执行建造命令后，到达指定地点后需要持续进行建造，直到SCV将建筑建造完成后才能执行下一个命令。
工蜂在开始执行建造命令后，到达指定地点后会自行开始一段时间的变异，变异结束后，将永久的失去这个工蜂，但建筑建造完成。
探机在开始执行建造命令后，只用在指定地点添加折跃(warp)空间标记，随后建筑将自行进行"折跃(warp)"，探机就可以去执行其他任务，经过一段的时间后，该建筑将自己完成"折跃"并可以使用，这时认为该建筑修建完毕。
因此，星灵建造建筑是最便捷的。
在星际争霸2中，有一种游戏模式是模式。合作模式中，有一种任务叫突变任务。突变任务指的是，在普通的合作任务下，增加了一些"突变因子"(额外的条件)，使得任务难度加大。每周的"突变因子"都不一样。
本周的"突变因子"，是给每个农民设定了一个疲劳属性，同时，你的所有建筑都只能建造在一个数轴上。
农民的疲劳值初始为0，每次该农民移动一个位置，消耗的时间为2*p+1秒，p表示当前疲劳值，在移动结束之后，疲劳值会增加1。当农民停下移动执行建造命令时，该农民的疲劳值会清0。
在本周的突变任务中，tokitsukaze控制着星灵单位。
tokitsukaze想要在一个基地的右侧建造n个水晶塔(Pylon)，水晶塔的折跃时间为k秒。
在这个突变任务里，她可以将一个农民部署在任何一个位置，这个农民每次可以向左或者向右移动1。如果该农民位于数轴坐标为x的位置，那么它每次可以移动到x-1或者x+1的位置(农民的初始疲劳值为0)。
现在给你tokitsukaze想要建造n个水晶塔的位置，请你安排一个合理的修建顺序，使得tokitsukaze建造完所有水晶塔的总时间最小（完成建造是指所有建造折跃完毕）。
输入描述:
第一行输入一个T(1≤T≤20)，表示有T组数据。 对于每组数据，第一行是两个正整数n,k(1≤n≤1000,1≤k≤10^5)，表示tokitsukaze想要建造n个水晶塔，并且每个水晶塔的折跃时间为k。 接下来一行n个用空格隔开的正整数pos[i](1≤pos[i]≤10000)，表示第i个水晶塔的位置为pos[i]。
输出描述:
对于每组数据，tokitsukaze建造所有建筑最少花费多少时间。
示例1
输入
复制
2 3 3 2 1 6 1 20 15
输出
复制
20 20
说明
对于第一个样例，tokitsukaze的最优策略为： 1、先将农民部署在1，然后农民直接修建2号水晶塔，然后农民无需等待，直接向右移动一个单位到达2，水晶塔会自行完成后续的折跃工作，此时总用时为1秒，农民的疲劳值为1。 2、农民在2修建1号水晶塔，疲劳值清零，然后再向右移动一个单位到达3，此时总用时为2秒，农民的疲劳值为1。 3、农民从3移动到4，此时总用时为5秒，农民的疲劳值为2。 4、农民从4移动到5，此时总用时为10秒，农民的疲劳值为3。 5、农民从5移动到6，此时总用时为17秒，农民的疲劳值为4。 6、农民在6修建3号水晶塔，疲劳值清零，然后等待3号水晶塔折跃完成。 7、由于3号水晶塔是最后进行折跃的水晶塔，所以当3号水晶塔进行完折跃后结束任务，3号水晶塔折跃完成时总用时为20秒。 对于第二个样例，tokitsukaze的最优策略为： 先将农民部署在15，然后直接修建水晶塔，然后等待水晶塔折跃完毕，总用时20秒。
#include<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long ll;
ll cal(int x){
return (2*(x-1)+1+1)*x/2;
}
/*
疲劳值: 0,1,2,3,4，……
时间: 1,3,5,7,9，……
步数: 1,2,3,4,5，……
分析：由于农民可以随便放，所以放最左边的塔效率最快
*/
int main(){
int T;
cin>>T;
int pos[1001];
while(T--){
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>pos[i];
}
sort(pos+1,pos+1+n);
ll sum=0;
for(int i=1;i<n;i++){
sum+=cal(pos[i+1]-pos[i]);
}
sum+=k;
cout<<sum<<"\n";
}
return 0;
}