luogu-P1023 税收与补贴问题

NOIP 2000 普及组真题，综合考察分段线性插值、利润建模与线性不等式求解。解题核心是：对每个竞争价格推导出税/补贴金额 $t$ 的线性约束，求所有约束的交集，最终取绝对值最小的整数 $t$ 。适合GESP五级以上考生练习。题目难度⭐⭐⭐，洛谷难度等级普及/提高−。

luogu-P1023 [NOIP 2000 普及组] 税收与补贴问题

题目要求

题目描述

每样商品的价格越低，其销量就会相应增大。已知某种商品的成本及其在若干价位上的销量，假设相邻价位间销量的变化是线性的，且在价格高于给定的最高价位后，销量以某固定数值递减。价格及销售量都是整数。产品不会低于成本销售。
你需要确定政府对此商品是应收税还是补贴的最少金额（整数），才能使商家在政府预期的价格上获取相对其他价位上的最大总利润。
总利润 $=$ 单位商品利润 $\times$ 销量
单位商品利润 $=$ 单位商品价格 $-$ 单位商品成本（减去税金或者加上补贴）

输入格式

第一行：政府预期价格。
第二行：商品成本、以成本价销售时的销售量。
接下来若干行：每行一个价位和对应销量，以 -1 -1 结束。
最后一行：超过最高价位后每升高一元减少的销量。

输出格式

若能使预期价获得最大总利润，输出一个整数（正数表示补贴，负数表示收税，绝对值最小）；若有多解，取绝对值最小的。否则输出 NO SOLUTION。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

数据范围：所有输入数字均小于 $10^5$ 。
样例解释：补贴 $4$ 元后，定价 $31$ 元时利润 = $(31-28+4) \times 110 = 770$ 元，是所有价位中最大的。

【题目来源】

NOIP 2000 普及组第三题

题目分析

这道题涉及分段线性函数的构建、利润模型的建立以及线性约束的推导，是一道综合性较强的模拟题。

1. 构建销量函数

根据题意，销量是价格的分段线性函数，需要分三段处理：

价格 < 成本：不可能销售，销量为 $0$ 。
已知价位之间：相邻价位间线性插值。例如已知 $(28, 130)$ 和 $(30, 120)$ ，则 $29$ 处的销量为 $130 + \frac{29-28}{30-28} \times (120-130) = 125$ 。
超过最高价位：每升高一元，销量减少固定值 dec，直到降为 $0$ 。

2. 利润模型

设政府给予的税/补贴金额为 $t$ （ $t > 0$ 为补贴， $t < 0$ 为收税），则在价格 $p$ 处的总利润为：

\text{profit}(p) = (p - \text{cost} + t) \times \text{sales}(p)

我们的目标是：找到绝对值最小的整数 $t$ ，使得预期价格 $\text{ep}$ 处的总利润 $\geq$ 所有其他价格处的总利润。

3. 核心转化——线性约束

对于每个竞争价格 $p$ （ $p \neq \text{ep}$ ， $\text{sales}(p) > 0$ ），我们需要：

(\text{dep} + t) \times s_{\text{ep}} \geq (d_p + t) \times s_p

其中 $\text{dep} = \text{ep} - \text{cost}$ ， $d_p = p - \text{cost}$ ， $s_{\text{ep}} = \text{sales}(\text{ep})$ ， $s_p = \text{sales}(p)$ 。

展开并移项：

t \times (s_{\text{ep}} - s_p) \geq d_p \times s_p - \text{dep} \times s_{\text{ep}}

记 $\text{diff} = s_{\text{ep}} - s_p$ ， $\text{numer} = d_p \times s_p - \text{dep} \times s_{\text{ep}}$ ，则约束为 $t \times \text{diff} \geq \text{numer}$ ，分三种情况：

情况	条件	约束	含义
A	$\text{diff} > 0$ （预期价销量更高）	$t \geq \lceil \text{numer} / \text{diff} \rceil$	$t$ 有下界
B	$\text{diff} < 0$ （预期价销量更低）	$t \leq \lfloor \text{numer} / \text{diff} \rfloor$	$t$ 有上界
C	$\text{diff} = 0$ （销量相同）	需要 $\text{numer} \leq 0$	否则无解

情况 A 通常来自价格高于预期价的竞争价（销量更低， $s_p < s_{\text{ep}}$ ），补贴越多越有利于高销量的预期价。

情况 B 通常来自价格低于预期价的竞争价（销量更高， $s_p > s_{\text{ep}}$ ），补贴太多反而让低价高销量的竞争者更强。

4. 求解最优 $t$

收集所有约束后：

$\text{lo} = \max(\text{所有下界})$
$\text{hi} = \min(\text{所有上界})$

还需补充一条约束：预期价的利润需 $\geq 0$ （否则"不卖"的利润 $0$ 更优），即 $t \geq -\text{dep}$ 。

若 $\text{lo} > \text{hi}$ 或出现情况 C 的无解，输出 NO SOLUTION。否则在 $[\text{lo}, \text{hi}]$ 中选取绝对值最小的整数 $t$ ：

若 $\text{lo} \leq 0 \leq \text{hi}$ ： $t = 0$ （无需税收也无需补贴）
若 $\text{lo} > 0$ ： $t = \text{lo}$ （最小补贴）
若 $\text{hi} < 0$ ： $t = \text{hi}$ （最小收税）

5. 样例演绎

输入：预期价 $31$ ，成本 $28$ ，数据点 $(28,130),(30,120),(31,110)$ ，超出后每元减少 $15$ 。

$\text{dep} = 3$ ， $s_{\text{ep}} = 110$ 。有效价格范围 $28 \sim 38$ （ $38$ 处销量 $= 110 - 15 \times 7 = 5 > 0$ ）。

价格 $p$	$d_p$	$s_p$	diff	numer	约束
28	0	130	$-20$	$-330$	$t \leq 16$
29	1	125	$-15$	$-205$	$t \leq 13$
30	2	120	$-10$	$-90$	$t \leq 9$
32	4	95	$15$	$50$	$t \geq 4$
33	5	80	$30$	$70$	$t \geq 3$
$\vdots$					$\vdots$

汇总： $\text{lo} = 4$ （来自 $p=32$ ）， $\text{hi} = 9$ （来自 $p=30$ ）。补充约束 $t \geq -3$ ，不影响 $\text{lo}$ 。

$\text{lo} > 0$ ，所以 $t = \text{lo} = 4$ （补贴 $4$ 元）。✅

验证： $t = 4$ 时， $p=31$ 利润 $= 7 \times 110 = 770$ ； $p=32$ 利润 $= 8 \times 95 = 760$ ； $p=30$ 利润 $= 6 \times 120 = 720$ 。预期价确实最优。

6. 特殊情况

$\text{dec} = 0$ 且最高价位仍有销量：价格可以无限上涨且销量不变，利润无上限，输出 NO SOLUTION。
情况 C 无解：存在某价格 $p$ ，销量与预期价完全相同但单价更高（ $d_p > \text{dep}$ ），无论 $t$ 取何值都无法让预期价胜出。
整数取整：上界用 $\lfloor \rfloor$ （向下取整），下界用 $\lceil \rceil$ （向上取整），确保约束严格满足。

7. 复杂度分析

时间复杂度： $O(N)$ ， $N$ 为有效价格的个数（从成本到销量降为 $0$ 的最高价格），一次遍历即可收集所有约束。
空间复杂度： $O(K)$ ， $K$ 为已知价位数据点数。

示例代码

#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>

int main() {
    // ========== 第一步：读取输入 ==========

    int ep; // 政府预期价格（希望商家以此价格销售）
    std::cin >> ep;

    int cost, s0; // cost: 商品成本价, s0: 以成本价销售时的销量
    std::cin >> cost >> s0;

    // 读取所有已知的 (价格, 销量) 数据点，存入 pts 数组
    // 首先将 (成本价, 成本价销量) 作为第一个数据点加入
    std::vector<std::pair<int, int>> pts;
    pts.push_back({cost, s0});

    // 循环读取后续数据点，直到遇到 (-1, -1) 终止标记
    int p, s;
    while (std::cin >> p >> s && !(p == -1 && s == -1)) {
        pts.push_back({p, s});
    }

    int dec; // 超过已知最高价位后，每升高一元钱，销量减少的数量
    std::cin >> dec;

    // ========== 第二步：构建销量函数 ==========

    // 将数据点按价格从小到大排序，方便后续线性插值
    std::sort(pts.begin(), pts.end());

    int maxP = pts.back().first;   // 已知数据点中的最高价位
    int maxS = pts.back().second;  // 最高价位对应的销量

    // 特判：若超过最高价位后销量不减少(dec=0)，且最高价位仍有销量
    // 则意味着价格可以无限上涨而销量不变，利润可以无限增长
    // 此时无论 t 取何值，总有更高价格的利润更大，预期价永远无法最优 → 无解
    if (dec == 0 && maxS > 0) {
        std::cout << "NO SOLUTION" << std::endl;
        return 0;
    }

    // getSales(price): 分段线性函数，计算任意整数价格 price 处的销量
    // 分三种情况：
    //   1. price < cost → 不允许低于成本销售，销量为 0
    //   2. price 在已知数据点范围内 → 相邻数据点之间做线性插值
    //   3. price > maxP → 超出最高价位，按 dec 递减，最低为 0
    auto getSales = [&](int price) -> int {
        // 低于成本价，不可销售
        if (price < cost) return 0;

        // 超过已知最高价位，按固定速率递减
        // 例如 maxP=31, maxS=110, dec=15，则 price=33 时销量 = 110 - 15*(33-31) = 80
        if (price > maxP) {
            int v = maxS - dec * (price - maxP);
            return v > 0 ? v : 0; // 销量不能为负
        }

        // 在已知数据点之间，找到 price 所在的区间并线性插值
        // 例如数据点 (28,130) 和 (30,120)，则 price=29 时：
        //   销量 = 130 + (29-28) * (120-130) / (30-28) = 130 + (-10)/2 = 125
        for (int i = 0; i + 1 < (int)pts.size(); i++) {
            if (price >= pts[i].first && price <= pts[i + 1].first) {
                int x1 = pts[i].first, y1 = pts[i].second;     // 左端点
                int x2 = pts[i + 1].first, y2 = pts[i + 1].second; // 右端点
                if (x1 == x2) return y1; // 两个数据点价格相同（退化情况）
                // 线性插值公式：y1 + (price - x1) * (y2 - y1) / (x2 - x1)
                // 使用 long long 防止中间乘法溢出
                return y1 + (long long)(price - x1) * (y2 - y1) / (x2 - x1);
            }
        }
        return maxS; // 理论上不会执行到这里
    };

    // ========== 第三步：推导 t 的约束范围 ==========

    int se = getSales(ep); // 预期价格处的销量
    int de = ep - cost;     // 预期价格与成本的差（即无税/补贴时的单位利润）

    // 计算需要检查的最高价格（销量仍然 > 0 的最高整数价格）
    // 例如 maxP=31, maxS=110, dec=15 → topPrice = 31 + (110-1)/15 = 31 + 7 = 38
    // 价格 38 处销量 = 110 - 15*7 = 5 > 0，价格 39 处销量 = 110 - 15*8 = -10 < 0
    int topPrice = maxP;
    if (dec > 0 && maxS > 0) {
        topPrice = maxP + (maxS - 1) / dec;
    }

    // lo 和 hi 分别记录 t 的下界和上界
    // 初始化为极小值和极大值（除以 2 防止后续运算溢出）
    long long lo = LLONG_MIN / 2; // t 的下界（t >= lo）
    long long hi = LLONG_MAX / 2; // t 的上界（t <= hi）
    bool noSol = false;           // 是否已确定无解

    // 遍历所有有效价格 pr（从成本价到最高有效价格）
    // 对于每个竞争价格 pr，推导出对 t 的约束
    for (int pr = cost; pr <= topPrice && !noSol; pr++) {
        if (pr == ep) continue; // 跳过预期价格本身
        int sp = getSales(pr);
        if (sp <= 0) continue;  // 销量 <= 0 的价格无利润，不构成竞争威胁
        int dp = pr - cost;     // 该价格与成本的差

        // 核心不等式：(de + t) * se >= (dp + t) * sp
        // 展开后移项：t * (se - sp) >= dp * sp - de * se
        // 记 diff = se - sp, numer = dp * sp - de * se
        // 则约束为：diff * t >= numer
        long long numer = (long long)dp * sp - (long long)de * se;
        int diff = se - sp;

        if (diff == 0) {
            // 情况 C：预期价格与竞争价格的销量完全相同
            // 此时约束退化为 0 * t >= numer，即 numer <= 0
            // 若 numer > 0，意味着无论 t 取何值，竞争价格的利润都更高 → 无解
            if (numer > 0) noSol = true;
        } else if (diff > 0) {
            // 情况 A：预期价格的销量更高（se > sp，通常 pr > ep）
            // 不等号方向不变：t >= numer / diff
            // 取整数下界：t >= ceil(numer / diff)
            long long bound;
            if (numer >= 0) {
                // 正数除正数，向上取整：(numer + diff - 1) / diff
                bound = (numer + diff - 1) / diff;
            } else {
                // 负数除正数，C++ 整数除法自动向零取整，即为向上取整
                bound = -((-numer) / diff);
            }
            lo = std::max(lo, bound); // 更新 t 的下界
        } else {
            // 情况 B：预期价格的销量更低（se < sp，通常 pr < ep）
            // diff < 0，除以负数不等号反向：t <= numer / diff
            // 将分子分母同时取反，转化为正除数：t <= (-numer) / (-diff)
            // 取整数上界：t <= floor((-numer) / (-diff))
            long long nn = -numer, nd = (long long)(-diff);
            long long bound;
            if (nn >= 0) {
                // 正数除正数，C++ 整数除法自动向零取整，即为向下取整
                bound = nn / nd;
            } else {
                // 负数除正数，需手动向下取整：-((-nn + nd - 1) / nd)
                bound = -((-nn + nd - 1) / nd);
            }
            hi = std::min(hi, bound); // 更新 t 的上界
        }
    }

    // 补充约束：预期价格的总利润必须 >= 0
    // 因为销量为 0 的价格利润恒为 0，若预期价利润 < 0 则不是最优
    // 总利润 = (de + t) * se >= 0，当 se > 0 时要求 t >= -de
    if (se > 0) {
        lo = std::max(lo, (long long)(-de));
    }

    // ========== 第四步：输出结果 ==========

    if (noSol || lo > hi) {
        // 无解：存在无法满足的约束（情况 C），或约束范围为空（下界 > 上界）
        std::cout << "NO SOLUTION" << std::endl;
    } else {
        // 在可行范围 [lo, hi] 中，选取绝对值最小的整数 t
        long long t;
        if (lo <= 0 && hi >= 0) {
            t = 0; // 0 在范围内，无需税收也无需补贴
        } else if (lo > 0) {
            t = lo; // 范围全在正半轴，取最小正值（最少补贴）
        } else {
            t = hi; // 范围全在负半轴，取最大负值（最少收税，即绝对值最小）
        }
        // 输出结果：正数表示补贴，负数表示收税
        std::cout << t << std::endl;
    }

    return 0;
}

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

GESP/CSP 认证学习微信公众号

最后更新于 2026年7月26日

luogu-P1022 计算器的改良