(差分约束) $O(nm)$

最大值跑最短路，a + c <= b, add(a, b, c)

最小值跑最长路，a + c >= b, add(a, b, c)

$\quad$学到提高课才知道能拿差分约束做

$\quad$这个模型从题意中很难推出来，我们来推一下公式

$\quad$设第一天各商家的物价为数组$a[N]$ , 第二天各商家物价为数组$b[N]$

$\quad$则由题意可以轻易得到
$\quad$$\quad$$\quad$1.从第2天到第n-1天的递推式为
$\quad$$\quad$$\quad$$\quad$$\quad$ $b[i]=(a[i+1]+a[i]+a[i-1])/3$
$\quad$$\quad$$\quad$2.第1天的递推式为
$\quad$$\quad$$\quad$$\quad$$\quad$ $b[1]=(a[1]+a[2])/2$
$\quad$$\quad$$\quad$3.第n天的递推式为
$\quad$$\quad$$\quad$$\quad$$\quad$ $b[n]=(a[n-1]+a[n])/2$

$\quad$然而！题意里要求的$b[i]=(a[i-1]+a[i]+a[i+1])/3$后下取整！

$\quad$这就表示我们的$a[i-1]+a[i]+a[i+1]$是有一个波动范围的,在这个范围内波动都能满足

$\quad$$\quad$$\quad$$\quad$$\quad$ $b[i]=(a[i-1]+a[i]+a[i+1])/3$

$\quad$而这个范围可以简化成这样

$\quad$$\quad$$\quad$1.第2天到第n-1天
$\quad$$\quad$$\quad$$\quad$3b[i]<=a[i-1]+a[i]+a[i+1]<=3b[i]+2
$\quad$$\quad$$\quad$2.第1天
$\quad$$\quad$$\quad$$\quad$2b[1]<=a[1]+a[2]<=2b[1]+1
$\quad$$\quad$$\quad$3.第n天
$\quad$$\quad$$\quad$$\quad$2b[n]<=a[n-1]+a[n]<=2b[n]+1

注意 题目给出的是b数组 我们要求的是a数组 固是a数组波动

$\quad$然后用前缀和技巧处理一下$a[i-1]+a[i]+a[i+1]=S[i+1]-S[i-2]$

$\quad$则我们就可以化简出四个约束条件

$\quad$$\quad$1. 3b[i]<=S[i+1]-S[i-2]<=3b[i]+2

$\quad$$\quad$2. 2b[1]<=S[2]-S[0]<=2b[1]+1

$\quad$$\quad$3. 2b[n]<=S[n]-S[n-2]<=2b[n]+1

$\quad$$\quad$4. S[i]-S[i-1]>=1

$\quad$将其转化为差分约束标准格式即为

$\quad$$\quad$1. S[i-2]+3b[i]<=S[i+1]
$\quad$$\quad$2. S[i+1]-(3b[i]+2)<=S[i-2]
$\quad$$\quad$3. S[0]+2b[1]<=S[2]
$\quad$$\quad$4. S[2]-(2b[1]+1)<=S[0]
$\quad$$\quad$5. S[n-2]+2b[n]<=S[n]
$\quad$$\quad$6. S[n]-(2b[n]+1)<=S[n-2]
$\quad$$\quad$7. S[i-1]+1<=S[i]

$\quad$然后跑一遍spfa,就行了

$\quad$注意！要求的是字典序最小值,也就是每个数都是可行解的最小值,故要使用spfa求最长路来解

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 310,M=1e5+10;
int h[N], e[M], w[M], ne[M], idx;
int q[N], dist[N];
bool st[N];
int b[N];
int n;

void add(int a, int b, int c)  // 添加一条边a->b，边权为c
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}


void spfa()  // 求1号点到n号点的最短路距离
{
    int hh = 0, tt = 0;
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    q[tt ++ ] = 0;


    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (dist[j] <dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])     // 如果队列中已存在j，则不需要将j重复插入
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}


int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i ++ ) scanf("%d",&b[i]);
    memset(h, -1, sizeof h);

    for(int i=2;i<n;i++){
        add(i-2,i+1,3*b[i]);
        add(i+1,i-2,-3*b[i]-2);
    }

    add(0,2,2*b[1]),add(2,0,-2*b[1]-1);
    add(n-2,n,2*b[n]),add(n,n-2,-2*b[n]-1);

    for(int i=1;i<=n;i++) add(i-1,i,1);

    spfa();
    for(int i=1;i<=n;i++) cout<<dist[i]-dist[i-1]<<' ';

    return 0;
}