2023.8.13百度之星（第二场）第一题官方题解注释说明

第一题：星际航行

#include 

using namespace std;
int n, a[3][100010];
int tmp[100010];
long long calc(int *a,int opt){//opt等于0表示回合到同一个点花费的最小代价，opt等于1表示将数列排序成连续的整数数列
    for(int i=1;i<=n;i++) tmp[i]=a[i];//复制一份
    sort(tmp+1,tmp+1+n);//先排序
    if(opt){
        for(int i=1;i<=n;i++) tmp[i]-=i;
        sort(tmp+1,tmp+1+n);
    }
    long long ans=0;
    for(int i=1;i<=n;i++) ans+=abs(tmp[i]-tmp[n/2+1]);//tmp[n/2+1]即表示选取中位数，用各坐标减去中位数即为最小代价
    return ans;
}

int main( )
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",a[0]+i,a[1]+i,a[2]+i);
    }
    long long sum=0,_min=0x3f3f3f3f3f3f3f3f;//表示无穷大
    for(int i=0;i<3;i++){
        long long cur=calc(a[i],0);//把三维都汇合到某一点
        _min=min(_min,calc(a[i],1)-cur);//再把某一维变为连续整数序列的最小代价=即把某一维变为连续序列的代价-把某一维汇合到同一点的代价
        sum+=cur;
    }
    cout<<sum+_min<<endl;//把三维都汇合到某一点再加上把某一维变为连续整数序列所用的代价
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32