https://acm.ecnu.edu.cn/contest/92/problem/D/
D. 数蝌蚪Time limit per test: 2.0 seconds
Memory limit: 256 megabytes
有 n 个装着小蝌蚪的水缸排成一排，你拥有一个无限蝌蚪的袋子，可以往一个水缸里放入一只蝌蚪，也可以取出一只蝌蚪，求最少的操作数，使得每个水缸的蝌蚪数量形成一个公差为 k 等差数列。
第一行一个数 n,k(3⩽n⩽3×105,0⩽k⩽104)。第二行 n 个数，表示每个水缸里的蝌蚪数目(0⩽ai⩽104)。
输出最少操作次数。
蝌蚪的个数不能是负的。
题目大意：最多进行多少次加减能使给定数列成为一个等差为k的数列（每次只能加或减一）
题解：代数分析+列式求解 具体地：先假设第一个数不变，然后用数组a[i]记录下后面的数与应得的数的差值，这时对第一个数进行操作 减 x ，那么后面的数则应进行操作abs(a[i]-x)，则一共需要进行的操作次数是 abs(a[i]-x)从0到n-1的和,易知当x取数组a[i]的中位数时和最小，所以进行计算即可 [注意由改变后的数必须为非负数，所以需要对x的值进行限制] 1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 long long orz[300005]; 7 int main() 8 { 9 long long n,k; 10 scanf("%lld%lld",&n,&k); 11 long long a; 12 scanf("%lld",&a); 13 long long A=a; 14 orz[0]=0; 15 int q=0,w=0; 16 for(int i = 1 ; i < n ; i++){ 17 long long b; 18 scanf("%lld",&b); 19 orz[i]=-(b-k-A); 20 A=A+k; 21 } 22 long long sum=0; 23 sort(orz,orz+n); 24 long long aa=0; 25 long long asd=max(aa,(1-n)*k); 26 long long ass=a-asd; 27 // cout << asd << endl; 28 if(orz[n/2]>ass){ 29 for(int i = 0 ; i < n ;i++){ 30 sum+=abs(orz[i]-ass); 31 } 32 33 34 } 35 else{ 36 for(int i = 0 ; i < n ;i++){ 37 sum+=abs(orz[i]-orz[n/2]); 38 } 39 } 40 41 cout << sum <<endl; 42 return 0; 43 } View Code
转载于:https://www.cnblogs.com/MekakuCityActor/p/9301667.html
