P8345 「Wdoi-6」华胥之梦

· · 题解

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 的一条最短的简单路径，满足其经过点集中所有点，并输出它的长度。

【数据范围】

看到这个题意和这个数据范围，感觉没有任何思路，不妨从特殊性质入手先拿部分分。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;
}