Problem E: yesky wine展销会打代码的憨憨-

来源：浙江理工大学程序设计校赛同步赛

浙江理工大学程序设计校赛同步赛

注：

听反馈说同步赛的数据少了，然后这个代码只能拿98，辩证的参考着看看吧，如果有ac的代码推个给我学习下，嘻嘻~

题目描述

懒羊羊的酒吧生意越来越好，也大量采购了ACM届教练叶老师的yesky wine葡萄酒。为了让更多羊村的村民及亲戚朋友方便品尝，不出现某些摊位拥挤有些摊位空闲，所以懒羊羊决定对酒吧的摊位重新排列，使得它们能均匀分布。这些摊位是排在一条直线上的。他了解了所有摊位的坐标，希望移动一些摊位，使得每2个相邻的摊位距离正好是K米。当然懒羊羊希望总的移动米数最小。

输入

第一行输入2个整数n和k(1<=n,k<=10^6),n代表酒吧摊位，k是希望移动后的2个相邻摊位距离
第二行输入n个不同的整数x1,x2,…,xn(-10^6<=xi<=106),代表原先的摊位坐标

输出

输出一个整数代表所有摊位移动到合理位置后总的最小移动米数

输入样例

【输入样例1】
3 1
2 5 7
【输入样例2】
10 4
140 26 69 55 39 64 2 89 78 421

输出样例

【输出样例1】
3
【输出样例2】
511

代码：

#include <iostream> #include<bits/stdc++.h> using namespace std; typedef long long int ll; const int N=1e6; ll ai[N+5],bi[N+5],ci[N+5],sum; int main() {     ios::sync_with_stdio(false);     cin.tie(0); int n,k;     cin>>n>>k; for(int i=1;i<=n;i++){         cin>>ai[i]; } sort(ai+1,ai+n+1); for(int i=1;i<=n;i++){         bi[i]=ai[i],ci[i]=ai[i]; } if(n%2==1) { int mid=n/2+1; for(int i=mid-1;i>=1;i--) {             sum+=abs(ai[i+1]-k-ai[i]);             ai[i]=ai[i+1]-k; } for(int i=mid+1;i<=n;i++) {             sum+=abs(ai[i]-k-ai[i-1]);             ai[i]=ai[i-1]+k; }         cout<<sum; } else { int mid_1=n/2,mid_2=n/2+1;         ll sum_1=0,sum_2=0; for(int i=mid_1-1;i>=1;i--) {             sum_1+=abs(bi[i+1]-k-bi[i]);             bi[i]=bi[i+1]-k; } for(int i=mid_1+1;i<=n;i++) {             sum_1+=abs(bi[i]-k-bi[i-1]);             bi[i]=bi[i-1]+k; } for(int i=mid_2-1;i>=1;i--) {             sum_2+=abs(ci[i+1]-k-ci[i]);             ci[i]=ci[i+1]-k; } for(int i=mid_2+1;i<=n;i++) {             sum_2+=abs(ci[i]-k-ci[i-1]);             ci[i]=ci[i-1]+k; }         cout<<min(sum_1,sum_2); } return 0; } 

心得：

这题刚开始关系没拎清，后来得到了为大佬指点，然后写了出来。思路就是先排序，n为奇数时去中间数，n为偶数是考虑两种情况取最小的，每个步骤中的两个循环是以mid为标杆向外扩展。