题解：寻找魔法坐标

题目描述

在平行的世界里，芙芙是一位热爱魔法和数字的年轻女巫。她希望为她的花园找到最佳位置，花园中的每朵花都有编号，从1到n。芙芙想要找到两个魔法坐标x和y，使得y-x=l，并且所有花的魔法力量之和最小。魔法力量f_i定义为花i与坐标x和y之间的最小距离。

输入输出描述

• 输入：包含多组测试数据，每组包含两个整数n和l（1≤n,l≤1000）。
• 输出：对于每组数据，输出一个整数，代表最小的f_1+f_2+...+f_n。

算法逻辑

问题分析

• 难点：如何选取x和y使得所有花的魔法力量之和最小。
• 关键思路：找到数组中位数，使得x和y分别位于中位数两侧，且y=x+l。

步骤

1. 计算中位数：根据n的奇偶性计算中位数mid。
2. 确定x和y：根据 l 的奇偶性，确定 x 和 y 的值。如果 l 为偶数，则 x 和 y 分别位于中位数两侧等距离的位置；如果 l 为奇数，则 y 比 x 多一个单位。
3. 计算魔法力量之和：对每个编号a_i，计算其与x和y的最小距离并累加。
4. 比较两种情况：由于 x 和 y 的选择有两种情况（一种情况是 x 和 y 位于中位数两侧，另一种是 x 和 y 位于中位数及其后 l 个位置），需要计算这两种情况下的魔法力量之和，并取较小值。

代码实现

#include<bits/stdc++.h>
using namespace std;
int mid,x,y;
int sum1,sum;
void calculate1(int n, int l) {
	if(n%2==0){
		mid=n/2;
		if(l%2==0){
			x=mid-(l/2);
			y=mid+l/2;
		}
		else{
			x=mid-(l/2);
			y=mid+l/2+1;
		}
	}
	else{
		mid=n/2+1;
		if(l%2==0){
			x=mid-(l/2);
			y=mid+l/2;
		}
		else{
			x=mid-(l/2);
			y=mid+l/2+1;
		}
	}
	
    
    sum1=0;
    for (int i=1;i<=n;i++) {
        sum1+=min(abs(i-x),abs(i-y));
    }
}
void calculate(int n, int l) {
	if(n%2==0){
		mid=n/2;
		if(l%2==0){
			x=mid;
			y=mid+l;
		}
		else{
			x=mid;
			y=mid+l;
		}
	}
	else{
		mid=n/2+1;
		if(l%2==0){
			x=mid;
			y=mid+l;
		}
		else{
			x=mid;
			y=mid+l;
		}
	}
    sum=0;
    for (int i=1;i<=n;i++) {
        sum+=min(abs(i-x),abs(i-y));
    }
}

 
int main() {
    int T;
    cin >> T; 
    while (T--) {
        int n,l;
        cin>>n>>l; 
        calculate(n,l);
		calculate1(n,l);
		if(sum>sum1) cout<<sum1<<endl;
		else cout<<sum<<endl; 
    }
    return 0;
}