货仓选址
显示标签
时间限制：C/C++ 1000MS，其他语言 2000MS
内存限制：C/C++ 256MB，其他语言 512MB
难度：简单
分数：100 OI排行榜得分：10(0.1分数+2难度)
出题人：
描述
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
输入描述
第一行输入整数 N。
第二行 N 个整数 A1∼AN。
输出描述
输出一个整数，表示距离之和的最小值。
用例输入 1
4
6 2 9 1
用例输出 1
12
提示
数据范围
1≤N≤100000,
0≤Ai≤40000
#include <iostream>
using namespace std;
int main()
{
int n;
int a[n+1];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int temp;
for(int i=n;i>0;i++)
{
for(int j=0;j<i;j++)
{
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
}
int zui=0,l=0;
for(int i=a[0];i<=a[n-1];i++)
{
for(int j=0;j<n;j++)
{
if(i>=a[j])
{
l=l+(i-a[j]);
}
else
{
l=l+(a[j]-i);
}
}
if(l<zui)
{
zui=l;
}
l=0;
}
cout<<zui;
}
排序是对的，但排序后的思路不对，让商店的位置和商店的位置比较是得不到最终结果的。
这题更多是数学思维，应该先分析，容易想到分类，商店是奇数和偶数的情况，很容易想到，如果商店是是偶数，仓库就在最中间的两个商店之间肯定最近，如果商店是奇数，那就建在最中间商店的位置。
这是想当然，我们可以用数学公式表示出来：
假设用c表示仓库，这个题它没考虑返回
那么最终求的就是
|A1-c| + |A2-c| + |A3-c| + |A4-c| + ... + |AN-c|
问题变成c取什么值时，式子取最小值呢？
其实容易观察到，我们把A1，A2都具体化成数轴上的点，假设A1就是1，A2就是2，A3就是3
那么当N=5时，|1-c| + |2-c| + |3-c| + |4-c| + |5-c| , c=3时有最小值，为1+5=6 2+4=6，c在中间，每一组取最小值
那么当N=6时，|1-c| + |2-c| + |3-c| + |4-c| + |5-c|+ |6-c| , c在3和4之间时有最小值，同理，c在中间，每一组取最小值
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
sort(a,a+n);//对所有商店按位置排序
int res=0;
for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);//n/2就是取所有商店中间的那个货仓，如果n是偶数，就取中间两个左边的一个，如果n是奇数，就是中间那个
cout<<res<<endl;
}
【以下回答由 GPT 生成】
代码的问题： 1. 第9行: 变量n没有初始化，会导致数组a的大小无法确定。 2. 第13行: 冒泡排序的终止条件应该是i>0而不是i>=0，否则会导致数组越界。 3. 第18行: 冒泡排序的内层循环应该是ji，否则会导致数组越界。 4. 第20行: 冒泡排序判断条件应该是a[j]a[j+1]，否则会导致数组逆序排列。 5. 第30行: 如果需要计算最小距离之和，初始值应该设为一个足够大的值，方便比较找到更小的值。 6. 第33行: 内层循环应该是从0开始而不是从1开始。 7. 第35-42行: 应该计算每个商店距离货仓的距离，并累加到l上，不需要判断i是否大于等于a[j]，只需要计算距离差的绝对值即可。 8. 第44行: 应该将l和zui比较的条件改为l>zui而不是l<zui，找到最小值时更新zui。 9. 第45行: 每次内层循环结束，将l重置为0。
优化建议： 1. 可以使用快速排序替换冒泡排序，可以更快地给数组排序。 2. 可以使用一次扫描找到数组中的最小值和最大值，不需要遍历整个数组来确定数轴的范围。 3. 可以使用动态数组代替静态数组，可以根据输入的n动态分配数组的大小。 4. 可以将寻找最小距离的过程进行优化，例如使用前缀和数组来计算距离之和，可以降低时间复杂度。
下面是修改后的代码：
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n;
cin >> n;
int* a = new int[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n); // 使用快速排序对数组进行排序
int minDistance = INT_MAX;
for (int i = a[0]; i <= a[n - 1]; i++)
{
int distance = 0;
for (int j = 0; j < n; j++)
{
distance += abs(a[j] - i); // 计算每个商店距离货仓的距离之和
}
minDistance = min(minDistance, distance); // 更新最小距离
}
cout << minDistance << endl;
delete[] a; // 释放分配的动态数组内存
return 0;
}
该代码中，使用快速排序对商店坐标进行排序，然后依次将货仓建在数轴上的每个位置，计算货仓到每家商店的距离之和，找到最小值并输出。代码在计算距离之和时，使用了绝对值函数来计算距离的绝对值。
希望这个回答对您有帮助。如果您有任何其他问题，请随时提问。
【相关推荐】