卖菜 - 题目列表

形式化题目

给定长度为 $n$ 的整数序列 $a_1, a_2, \dots, a_n$ 。构造新序列 $b_1, b_2, \dots, b_n$ ，满足

b_i = \begin{cases} \left\lfloor \dfrac{a_1 + a_2}{2} \right\rfloor, & i = 1,\\[4pt] \left\lfloor \dfrac{a_{i-1} + a_i + a_{i+1}}{3} \right\rfloor, & 2 \le i \le n - 1,\\[4pt] \left\lfloor \dfrac{a_{n-1} + a_n}{2} \right\rfloor, & i = n. \end{cases}

其中 $\lfloor \cdot \rfloor$ 表示去尾法向下取整。

思路

端点与中间分开处理

端点 $1$ 和 $n$ 各只有一个邻居，取两项的平均值；中间的每个位置取自己与左右邻居三项的平均值。用整数除法 a / b 即可实现向下取整。

新旧状态分离

所有 $b_i$ 都只依赖第一天的价格 $a$ 。因此必须先完整保存 $a$ ，再统一计算 $b$ ，不能在原数组上边算边覆盖。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;

int n;
int price[MAXN];      // 第一天各商店的菜价
int next_price[MAXN]; // 第二天各商店的菜价

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> price[i];
    }

    // 两端商店只有一个邻居，取两项的平均值。
    next_price[1] = (price[1] + price[2]) / 2;
    next_price[n] = (price[n - 1] + price[n]) / 2;

    // 中间商店取自己与左右邻居三项的平均值。
    for (int i = 2; i <= n - 1; i++) {
        next_price[i] = (price[i - 1] + price[i] + price[i + 1]) / 3;
    }

    for (int i = 1; i <= n; i++) {
        if (i > 1) cout << ' ';
        cout << next_price[i];
    }
    cout << '\n';

    return 0;
}

复杂度

时间：每个商店只计算一次， $O(n)$ 。
空间：保存两天的价格数组， $O(n)$ 。

总结

同步更新题的核心是区分旧状态和新状态：先完整读入旧值，再据此推出全部新值。两个端点的参与项数不同，单独处理即可，整数除法天然满足去尾规则。

卖菜

目录

形式化题目

思路

端点与中间分开处理

新旧状态分离

代码

复杂度

总结