时间限制(普通/Java):500MS/1500MS 内存限制:65536KByte
总提交: 25 测试通过:5
描述
有 n 个装着小蝌蚪的水缸排成一排，你拥有一个无限蝌蚪的袋子，可以往一个水缸里放入一只蝌蚪，也可以取出一只蝌蚪，求最少的操作数，使得每个水缸的蝌蚪数量形成一个公差为 k 等差数列。
输入
多组数据（<35），每组数据描述如下。
第一行一个数 n,k(1<=n<=10,0<=k=<10)。
第二行 n个数，表示每个水缸里的蝌蚪数目(0<=a<=10)。
输出
每组数据输出一个最少操作次数。
样例输入
4 2
1 2 3 4
4 2
0 1 2 3
样例输出
4
6
提示
蝌蚪的个数不能为负。
题解：
最多进行多少次加减操作能使给定数列成为一个公差为k的等差数列（每次只能加或减1）
首先，先将第一个数假设为一个定值，然后改变后面的值，得到一个公差为k的等差数列，用一个数组b去记录每一个数和它应得的数的差值，此时，对第一个数进行减x的操作，那么后面每一位数都要进行减x的操作，也就是abs(b[i]-x)，这个也就是每一位所要得到
应得值的次数，那么只要从0循环到n每一位都进行上述操作得到的和就是最少操作次数，x取数列中位数的时候，和为最小。但是因为应得的值都必须是正数，所以得考虑x的值，使得最后得到的数列每一位都是正数。
#include "bits/stdc++.h"
#define ll long long
using namespace std;
inline void read(int &x)
{
x=;char c=getchar();
while(c<'' || c>'')c=getchar();
while(c>='' && c<=''){
x=x*+c-'';
c=getchar();
}
}
inline void write(int x)
{
int y=,len=;
while(y<=x) {y*=;len++;}
while(len--){y/=;putchar(x/y+);x%=y;}
}
ll a[];
ll b[];
int main()
{
ll n,k;
while(~scanf("%I64d%I64d",&n,&k))
{
scanf("%I64d",&a[]);
//b[0]=a[0];
int p=a[];
b[]=;
for(int i=;i<n;++i)
{
scanf("%I64d",&a[i]);
//b[i]=b[i-1]+k-a[i]+b[i-1];
b[i]=p+k-a[i];
p+=k;
}
sort(b,b+n);
ll p1=a[];
ll res=;
if(b[n/]>p1)for(int i=;i<n;++i)res+=abs(b[i]-p1);
else for(int i=;i<n;++i)res+=abs(b[i]-b[n/]);
printf("%I64d\n",res);
}
}