本文共 4611 字，大约阅读时间需要 15 分钟。

在一条街上有n个卖菜的商店，按1至n的顺序排成一排，这些商店都卖一种蔬菜。

第一天，每个商店都自己定了一个正整数的价格。店主们希望自己的菜价和其他商店的一致，第二天，每一家商店都会根据他自己和相邻商店的价格调整自己的价格。具体的，每家商店都会将第二天的菜价设置为自己和相邻商店第一天菜价的平均值（用去尾法取整）。 注意，编号为1的商店只有一个相邻的商店2，编号为n的商店只有一个相邻的商店n-1，其他编号为i的商店有两个相邻的商店i-1和i+1。 给定第二天各个商店的菜价，可能存在不同的符合要求的第一天的菜价，请找到符合要求的第一天菜价中字典序最小的一种。 字典序大小的定义：对于两个不同的价格序列(a1, a2, …, an)和(b1, b2, b3, …, bn)，若存在i (i>=1), 使得ai<bi，且对于所有j<i，aj=bj，则认为第一个序列的字典序小于第二个序列。

Input

输入的第一行包含一个整数n，表示商店的数量。

第二行包含n个正整数，依次表示每个商店第二天的菜价。

Output

输出一行，包含n个正整数，依次表示每个商店第一天的菜价。

Examples

样例输入

8 2 2 1 3 4 9 10 13 样例输出 2 2 2 1 6 5 16 10

Hint

对于30%的评测用例，2<=n<=5，第二天每个商店的菜价为不超过10的正整数；

对于60%的评测用例，2<=n<=20，第二天每个商店的菜价为不超过100的正整数； 对于所有评测用例，2<=n<=300，第二天每个商店的菜价为不超过100的正整数。 请注意，以上都是给的第二天菜价的范围，第一天菜价可能会超过此范围。

题解:

之前以为CCF除了大模拟恶心都挺简单的…这道题改变了我对CCF这个认证考试的看法. 这道题放在ACM里面也算是一道银牌题了.

先说解法, 有两种, 一种是记忆化搜索, 纯暴力, 代码量大, 不推荐. 一种是差分约束, 属于图论算法中最短路径算法的一个分支, 不会的同学建议先去学一下,

题意很简单, 给出b数组求出a数组, 很容易根据b[i] = (a[i-1]+a[i]+a[i+1])/3 这样的递推关系式可以联想到暴力递推, 但是注意由a求b的去尾法取整这个问题, 这个是没有办法直接消去影响的, 所以直接暴力肯定不行.

但是解题的关键依然在于递推, 我们不妨先把所有的递推关系式列出来, 看看有什么思路.

$b[1]=(a[1]+a[2])/2(i=1)$ $b[n]=(a[n]+a[n-1])/2(i=n)$ $b[i]=(a[i-1]+a[i]+a[i+1])/3(1<i<n)$

由于是已知b求a, 所以上式等价于下式

$a[1]+a[2]>=2\ast b[1](i=1)$

$a[n-1]+a[n-2]>=2\ast b[n](i=1)$ $a[i-1]+a[i]+a[i+1]>=3\ast b[i](1<i<n)$

看到这里, 多个不等式只两边存在两种变量(b[i]已知所以是常量), 就要想到差分约束算法了. 但是对于$1<i<n$的情况, 不等式两边存在3个变量, 怎么办呢?

这里要想到前缀和, 即定义$sum[i]={\sum }_1^{i}a[i]$

上式就可以转化为

$sum[2]-sum[0]>=2\ast b[1]$ $sum[n-1]-sum[n-3]>=2\ast b[n]$ $sum[i+1]-sum[i-2]>=3\ast b[i]$

同时考虑到除法去尾, 还有考虑下面的不等式, 记得转为前缀和

$a[i]>=0即sum[i]-sum[i-1]>=1$ $2\ast b[1]<=a[1]+a[2]<=a[1]+a[2]+2$ $2\ast b[n]<=a[n]+a[n-1]<=a[n]+a[n-1]+2$ $3\ast b[i]<=a[i]+a[i-1]+a[i+1]<=a[i]+a[i-1]+a[i+1]+3$

接下来就完全可以用差分约束来解了

经验小结:

#include
   
    using namespace std;#define ms(x, n) memset(x,n,sizeof(x));typedef  long long LL;const int inf = 1 << 30;const int maxn = 310;int n, a[maxn], b[maxn], sum[maxn];struct Edge {
       int to, w;};vector
    
      es[maxn];void addEdge(int u, int v, int w) {
       es[u].push_back(Edge{
   v, w});}int d[maxn], cnt[maxn];//每个点的入队列次数bool used[maxn], is[maxn];bool SPFA() {
       queue
     
       q;    ms(is, 0);    for(int i = 0; i <= n; ++i){
           q.push(i);     //防止图不连通        used[i] = true, ++cnt[i], d[i] = 0;    }    while(!q.empty()) {
           int u = q.front();        q.pop();        used[u] = false;        for(int i = 0; i < es[u].size(); ++i) {
               int v = es[u][i].to, w = es[u][i].w;            if(!is[v] && d[u] + w > d[v]) {
                   d[v] = d[u] + w;                if(!used[v]) {
                       used[v] = true;                    q.push(v);                    if(++cnt[v] > n)  //大于n次说明存在负权回路                        return false;                }            }        }    }    return true;}int main() {
       cin >> n;    for(int i = 1; i <= n; ++i)        cin >> b[i];    //差分约束    addEdge(0, 2, 2*b[1]);  //单独处理1和n    addEdge(2, 0, -(2*b[1]+1));    addEdge(n-2, n, 2*b[n]);    addEdge(n, n-2, -(2*b[n]+1));    for(int i = 0 ;i < n-2; ++i){
           addEdge(i, i+3, 3*b[i+2]);        addEdge(i+3, i, -(3*b[i+2]+2));    }    for(int i = 1; i <= n; ++i)        addEdge(i-1, i, 1);    SPFA();    for(int i = 1; i <= n; ++i)        a[i] = d[i]-d[i-1];    cout << a[1];    for(int i = 2; i <= n; ++i)        cout << ' ' << a[i];    return 0;}
     
    
   

转载地址：https://suprit.blog.csdn.net/article/details/100837275 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！