自动搬运

查看原文

来自洛谷，原作者为

	victory_huyuehao WA不是Wrong Answer，而是Wonderful Answer。

搬运于2025-08-24 23:13:19，当前版本为作者最后更新于2025-04-19 12:07:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

新手的第一篇题解，请多多包涵！

更新： 2025 年 4 月 24 日，修改了 1 个错误，优化语言。

洛谷P12165

这是一道贪心，十分经典。

贪心思路

首先，对于输入的数据要升序排序，c++ 的 sort 函数就能解决。

通过观察，我们可以得出结论：第 $i$ 个显示器与第 $i$ 个插头连接时，距离最短。

但是，我们需要证明，可能会出现别的情况。

证明贪心

另一种情况：第 $1$ 个显示器与第 $n$ 个显示器连接，第 $2$ 与第 $n - 1$ 个连接……

这种情况有可能最优。

证明原来的思路很简单，举个反例。

假设 $A$ 为显示器，$B$ 为插头，$0$ 为空间隔。

那么这种情况：

      A 0 B A A B 0 B
位置：0 1 2 3 4 5 6 7

按照第 $1$ 个显示器与第 $n$ 个显示器连接，第 $2$ 个与第 $n - 1$ 个连接……可以得出充电线长度：

按照第 $i$ 个显示器与第 $i$ 个 插头连接，则：

很显然，反例是错误的，贪心成立。

代码如下：

C++代码

#include <bits/stdc++.h>
using namespace std;
int n,a[50010],b[50010];//定义，a为显示器位置，b为插头位置
long long cnt;//计数器
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++){
		scanf("%d",&b[i]);
	}//输入
	sort(a+1,a+n+1);
	sort(b+1,b+n+1);//排序
	for(int i=1;i<=n;i++){
		cnt+=abs(b[i]-a[i]);
	}//计数
	printf("%lld",cnt);
	return 0;
}

谢谢观看！