【NOIP】2000真题解析 luogu-P1023 税收与补贴问题(适合GESP四、五级以上练习)

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

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

题目要求

题目描述

每样商品的价格越低，其销量就会相应增大。已知某种商品的成本及其在若干价位上的销量，假设相邻价位间销量的变化是线性的，且在价格高于给定的最高价位后，销量以某固定数值递减。价格及销售量都是整数。产品不会低于成本销售。

你需要确定政府对此商品是应收税还是补贴的最少金额（整数），才能使商家在政府预期的价格上获取相对其他价位上的最大总利润。

• 总利润  单位商品利润  销量
• 单位商品利润  单位商品价格  单位商品成本（减去税金 或者 加上补贴）

输入格式

第一行：政府预期价格。

第二行：商品成本、以成本价销售时的销售量。

接下来若干行：每行一个价位和对应销量，以 -1 -1 结束。

最后一行：超过最高价位后每升高一元减少的销量。

输出格式

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

输入输出样例 #1

输入 #1

3128 13030 12031 110-1  -115

输出 #1

4

说明/提示

数据范围：所有输入数字均小于 。

样例解释：补贴  元后，定价  元时利润 =  元，是所有价位中最大的。

【题目来源】

NOIP 2000 普及组第三题

题目分析

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

1. 构建销量函数

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

• 价格 < 成本：不可能销售，销量为 。
• 已知价位之间：相邻价位间线性插值。例如已知  和 ，则  处的销量为 。
• 超过最高价位：每升高一元，销量减少固定值 dec，直到降为 。

2. 利润模型

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

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

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

对于每个竞争价格 （，），我们需要：

其中 ，，，。

展开并移项：

记 ，，则约束为 ，分三种情况：

情况 A 通常来自价格高于预期价的竞争价（销量更低，），补贴越多越有利于高销量的预期价。

情况 B 通常来自价格低于预期价的竞争价（销量更高，），补贴太多反而让低价高销量的竞争者更强。

4. 求解最优 

收集所有约束后：

还需补充一条约束：预期价的利润需 （否则"不卖"的利润  更优），即 。

若  或出现情况 C 的无解，输出 NO SOLUTION。否则在  中选取绝对值最小的整数 ：

• 若 ：（无需税收也无需补贴）
• 若 ：（最小补贴）
• 若 ：（最小收税）

5. 样例演绎

输入：预期价 ，成本 ，数据点 ，超出后每元减少 。

，。有效价格范围 （ 处销量 ）。

汇总：（来自 ），（来自 ）。补充约束 ，不影响 。

，所以 （补贴  元）。✅

验证： 时， 利润 ； 利润 ； 利润 。预期价确实最优。

6. 特殊情况

•  且最高价位仍有销量：价格可以无限上涨且销量不变，利润无上限，输出 NO SOLUTION。
• 情况 C 无解：存在某价格 ，销量与预期价完全相同但单价更高（），无论  取何值都无法让预期价胜出。
• 整数取整：上界用 （向下取整），下界用 （向上取整），确保约束严格满足。

7. 复杂度分析

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

示例代码

#include<algorithm>#include<climits>#include<iostream>#include<vector>intmain(){    // ========== 第一步：读取输入 ==========    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;}

“luogu-”系列题目可在洛谷题库进行在线评测。

“bcqm-”系列题目可在编程启蒙题库进行在线评测。