自动搬运

查看原文

来自洛谷，原作者为

	Dr_Gilbert 比赛审核事宜请在工单沟通，不要私信沟通。

搬运于2025-08-24 22:38:14，当前版本为作者最后更新于2022-05-17 11:24:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

P8345 「Wdoi-6」华胥之梦

UPD 2022-05-20: 修改一处笔误

【题目大意】

给定长度为 $n$ 的序列 $a$ 和常数 $c$。构造点数为 $n$ 的有向完全图 $G$ 使得边 $i\to j$（$i\neq j$）的长度为 $a_i-2a_j+c$，保证所有边权非负。

接下来给出 $q$ 次询问，每次给出一个点集，试找出图 $G$ 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。

【数据范围】

• $N,Q,\sum |S|\le10^6$。
• 对于 $20\%$ 的数据，有 $a_i$ 全部相同。
• 对于另 $20\%$ 的数据，有 $a_i$ 单调递增。

看到这个题意和这个数据范围，感觉没有任何思路，不妨从特殊性质入手先拿部分分。$a_i$ 全部相同的部分分非常简单，也没有什么价值。比较关键的是 $a_i$ 全部递增这点性质，由于边权的定义为 $a_i-2a_j+c$，不难想到一个贪心策略，那就是将点集中的点排序后直接走。如果这个策略正确，那么可以由这个策略推广，只需把点集中的点按 $a_i$ 的值升序排序后直接走即可。下面可以证明一下这个贪心策略。

这个贪心策略的证明，在这里分两部分，第一部分是论证若所走的点一定是点集内的点，则路径长度最短；而第二部分是若走的顺序一定按 $a_i$ 大小，则路径最短。先论证第一部分。注意到题目中保证所有边权非负数，即

$$a_i-2a_j+c\ge0$$

对这个式子进行一些变换，就可以得到

$$a_i-2a_j+c\ge0\Rightarrow a_j\le \frac{a_i+c}{2}$$

对于这条边的反向边 $j \rightarrow i$ ，同理有

$$a_i\le\frac{a_j+c}{2}$$

将上式中 $a_j$ 的最大值代入下式，有

$$a_i\le \frac{\frac{a_i+c}{2}+c}{2} \Rightarrow 4a_i\le a_i+3c \Rightarrow a_i\le c $$

显然，$a_i$ 随 $a_j$ 的增大而增大，所以 $a_i$ 的最大值为 $c$。假设在从点 $i$ 到 $j$ 时，经过了点 $k$，即路径为 $i\rightarrow k \rightarrow j$，则总长度为

$$a_i-2a_k+c+a_k-2a_j+c=a_i-a_k-2a_j+2c\\ \because a_k\le c\\ \therefore c-a_k\ge 0\\ \therefore a_i-a_k-2a_j+2c\ge a_i-2a_j+c $$

所以如果不需要经过点 $k$，那么就不要走点 $k$，即若所走的点一定是点集内的点，则路径长度最短，第一部分得证。接下来论证第二部分：

由第一部分的结论，最短路径上的点一定都在点集内。且由边权非负，可得所走路径一定是按某个顺序依次连接点集中所有点的一条链。所以对于点集 $S$，最短路径的边数是确定的，即 $|S|-1$。所以总代价中的常数项是确定的。接下来可以对某个点集中某条路径的总长度的式子进行简单推导，设点集中各点按一定顺序排列后分别为 $S(1)\ldots S(n)$，则这条路径的总路径长为

$$a_{S(1)}-2a_{S(2)}+a_{S(2)}-2a_{S(3)}+\cdots+a_{S(n-1)}-2a_{S(n)}+(n-1)c $$

化简得

$$(n-1)c+a_{S(1)}-2a_{S(n)}-\sum_{i=2}^{n-1} a_{S(i)} $$

可见，最终的路径长度只和路径的起点和终点有关。只需保证起点的 $a_i$ 最小且重点的 $a_i$ 最大，即可保证总长度最小，而排序就可以保证这一条件，第二部分得证。

当然，从第二部分的证明可以发现，完全没有必要对集合 $S$ 进行排序，只需找出最大值和最小值即可。这样，时间复杂度就降到了 $O(\sum|S|)$。

当然，这道题时限 $1.5 \text{ s}$，并没有卡每次排序的做法。赛时时间紧，没多想就写了每次排序的做法，时间复杂度 $O(n\log n+\sum |S|\log |S|)$。

代码如下：

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct po{
	int val,x;
	bool operator <(const po& a)const{
		return val<a.val;
	}
}p[1000010];
int s[1000010],a[1000010];
bool cmp(int x, int y){return (a[x]<a[y]);}
bool cmp2(po a, po b){return a.x<b.x;}
signed main(){
	int n,c,q;
	cin>>n>>c>>q;
	for (int i=1;i<=n;i++){
		cin>>p[i].val;
		p[i].x=i;
	}
	sort(p+1,p+1+n);//排序
	for (int i=1;i<=n;i++) a[p[i].x]=i; // 存排名
	sort(p+1,p+1+n,cmp2);
	while (q--){
		int k;cin>>k;
		for (int i=1;i<=k;i++) cin>>s[i];
		sort(s+1,s+1+k,cmp); // 按a_i从小到大
		int ans=0;
		for (int i=2;i<=k;i++){
			ans+=p[s[i-1]].val-2*p[s[i]].val+c;
		}
		cout<<ans<<endl;
	}
	return 0;
}