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

GitHub 跳转原题关系图返回列表

把每个竞争售价转成关于税收或补贴 k 的一次严格不等式，和目标价对应约束求交集后，直接取绝对值最小的整数解。

OJ: luogu

题目 ID: P1023

难度:普及+/提高

标签:模拟枚举分段函数思维

日期: 2026-06-20 09:42

题意

给出一个商品的成本价、若干个“售价-销量”已知点，以及超过最后一个已知点后销量的线性下降速度。

要求找到一个整数税收或补贴金额，使得商家把售价定在政府预期售价时，获得的总利润严格大于其他所有可选售价，并且这个税收/补贴金额的绝对值最小。

思路

先看一个可以直接验证想法的朴素解：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXM = 100005;

struct Fraction {
    i64 num; // 分子
    i64 den; // 分母，恒为正数
};

int target_price;
int point_cnt;
int tail_drop;
int raw_price[MAXM], raw_sale[MAXM];

// brute.cpp：教学用暴力。
// 直接枚举整数 k，并按题意计算每个价格下的销量和利润。

int cmp_fraction(Fraction a, Fraction b) {
    __int128 left = (__int128) a.num * b.den;
    __int128 right = (__int128) b.num * a.den;
    if (left < right) {
        return -1;
    }
    if (left > right) {
        return 1;
    }
    return 0;
}

Fraction get_sale_fraction(int x) {
    for (int i = 1; i < point_cnt; i++) {
        int x1 = raw_price[i];
        int y1 = raw_sale[i];
        int x2 = raw_price[i + 1];
        int y2 = raw_sale[i + 1];
        if (x1 <= x && x <= x2) {
            i64 num = 1LL * y1 * (x2 - x1) + 1LL * (y2 - y1) * (x - x1);
            i64 den = x2 - x1;
            return {num, den};
        }
    }

    int last_price = raw_price[point_cnt];
    int last_sale = raw_sale[point_cnt];
    return {1LL * last_sale - 1LL * tail_drop * (x - last_price), 1};
}

int get_upper_price() {
    int last_price = raw_price[point_cnt];
    int last_sale = raw_sale[point_cnt];
    if (tail_drop == 0) {
        return last_price;
    }
    return last_price + (last_sale - 1) / tail_drop;
}

// 返回售价 x 在税收/补贴 k 下的总利润。
// 这里利润也保存成分数，避免插值时的除法误差。
Fraction get_profit(int x, int k, int cost_price) {
    Fraction sale = get_sale_fraction(x);
    return {sale.num * (x - cost_price + k), sale.den};
}

bool check(int k, int cost_price, int upper_price) {
    if (target_price < cost_price || target_price > upper_price) {
        return false;
    }

    Fraction target_sale = get_sale_fraction(target_price);
    if (target_sale.num <= 0) {
        return false;
    }

    Fraction target_profit = get_profit(target_price, k, cost_price);

    for (int x = cost_price; x <= upper_price; x++) {
        if (x == target_price) {
            continue;
        }
        Fraction sale = get_sale_fraction(x);
        if (sale.num <= 0) {
            continue;
        }

        Fraction profit = get_profit(x, k, cost_price);
        if (cmp_fraction(profit, target_profit) >= 0) {
            return false;
        }
    }
    return true;
}

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

    cin >> target_price;
    while (true) {
        int x, y;
        cin >> x >> y;
        if (x == -1 && y == -1) {
            break;
        }
        raw_price[++point_cnt] = x;
        raw_sale[point_cnt] = y;
    }
    cin >> tail_drop;

    int cost_price = raw_price[1];
    int upper_price = get_upper_price();

    // 暴力范围开大一些，供随机对拍使用。
    for (int d = 0; d <= 2000; d++) {
        if (check(d, cost_price, upper_price)) {
            cout << d << '\n';
            return 0;
        }
        if (d != 0 && check(-d, cost_price, upper_price)) {
            cout << -d << '\n';
            return 0;
        }
    }

    cout << "NO SOLUTION\n";
    return 0;
}

这题本质上没有复杂数据结构，关键是把题意翻译成正确的不等式。

先约定：

k > 0 表示补贴
k < 0 表示税收
利润函数是：

profit(price) = (price - cost + k) * sale(price)

其中 sale(price) 是一个离散的分段线性函数：

在相邻给定点之间做整数线性插值
超过最后一个点后按固定斜率递减

设目标售价是 tp，某个竞争售价是 x，它们对应销量分别是 st 和 sx。

若目标价要严格更优，就必须满足：

(tp - cost + k) * st > (x - cost + k) * sx

移项后得到一个关于 k 的一次严格不等式：

k * (st - sx) > (x - cost) * sx - (tp - cost) * st

也就是说：

每个竞争价格 x 都会对 k 给出一个限制
所有限制同时成立时，目标价才会成为唯一最优点

于是做法变成：

写一个 get_sale(price)，按题意求出某个售价的销量
枚举所有可能和目标价竞争的整数售价 x
把“目标价利润严格大于 x 的利润”改写成对 k 的上下界限制
把所有限制求交集
在可行整数区间里取绝对值最小的 k

一个小表格

量	含义
`price`	商家选择的售价
`sale(price)`	该售价下的销量
`k`	税收/补贴金额，补贴为正，税收为负
`profit(price)`	总利润

这里还有两个细节：

题目要求的是严格最大，所以遇到“相等利润”也算不合法
如果目标价本身已经没有正销量，或者所有限制求交后区间为空，就输出 NO SOLUTION

代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180#include <bits/stdc++.h>
using namespace std;

using i64 = long long;

const int MAXM = 100005;
const i64 INF64 = (1LL << 60);

struct Fraction {
    i64 num; // 分子
    i64 den; // 分母，恒为正数
};

int target_price;
int point_cnt;
int tail_drop;
int raw_price[MAXM], raw_sale[MAXM];

// 比较两个分数 a 和 b 的大小，返回：
// -1: a < b
//  0: a = b
//  1: a > b
int cmp_fraction(Fraction a, Fraction b) {
    __int128 left = (__int128) a.num * b.den;
    __int128 right = (__int128) b.num * a.den;
    if (left < right) {
        return -1;
    }
    if (left > right) {
        return 1;
    }
    return 0;
}

// 计算 floor(a / b)，其中 b > 0，支持 a 为负数。
i64 floor_div(i64 a, i64 b) {
    if (a >= 0) {
        return a / b;
    }
    return -((-a + b - 1) / b);
}

// 计算 ceil(a / b)，其中 b > 0，支持 a 为负数。
i64 ceil_div(i64 a, i64 b) {
    if (a >= 0) {
        return (a + b - 1) / b;
    }
    return -((-a) / b);
}

// 返回售价 x 对应的销量。
// 为了避免中间插值产生误差，这里把销量写成分数。
Fraction get_sale_fraction(int x) {
    for (int i = 1; i < point_cnt; i++) {
        int x1 = raw_price[i];
        int y1 = raw_sale[i];
        int x2 = raw_price[i + 1];
        int y2 = raw_sale[i + 1];
        if (x1 <= x && x <= x2) {
            i64 num = 1LL * y1 * (x2 - x1) + 1LL * (y2 - y1) * (x - x1);
            i64 den = x2 - x1;
            return {num, den};
        }
    }

    int last_price = raw_price[point_cnt];
    int last_sale = raw_sale[point_cnt];
    return {1LL * last_sale - 1LL * tail_drop * (x - last_price), 1};
}

// 计算某个给定售价下，销量变成非正数前最后还需要检查到哪个价格。
int get_upper_price() {
    int last_price = raw_price[point_cnt];
    int last_sale = raw_sale[point_cnt];

    if (tail_drop == 0) {
        // 题面通常不会出现这种情况；若真的出现，销量不会继续下降，
        // 说明高价可以无限延伸，这时利润不会有唯一最大值。
        return last_price;
    }

    // 当销量 > 0 时才有意义，所以只需检查到最后一个正销量价格。
    return last_price + (last_sale - 1) / tail_drop;
}

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

    cin >> target_price;
    while (true) {
        int x, y;
        cin >> x >> y;
        if (x == -1 && y == -1) {
            break;
        }
        raw_price[++point_cnt] = x;
        raw_sale[point_cnt] = y;
    }
    cin >> tail_drop;

    int cost_price = raw_price[1];
    int upper_price = get_upper_price();

    // 目标价本身如果已经没有正销量，那么一定无解。
    Fraction target_sale = get_sale_fraction(target_price);
    if (target_price < cost_price || target_price > upper_price || target_sale.num <= 0) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    // 对每个竞争价格 x，都有：
    // (tp - cost + k) * st > (x - cost + k) * sx
    // 化简成：
    // k * (st - sx) > (x - cost) * sx - (tp - cost) * st
    // 这是关于 k 的一次严格不等式。
    i64 low = -INF64; // k 的下界，满足 k >= low
    i64 high = INF64; // k 的上界，满足 k <= high

    for (int x = cost_price; x <= upper_price; x++) {
        if (x == target_price) {
            continue;
        }

        Fraction sale_x = get_sale_fraction(x);
        if (sale_x.num <= 0) {
            continue;
        }

        __int128 a128 = (__int128) target_sale.num * sale_x.den - (__int128) sale_x.num * target_sale.den;
        __int128 b128 = (__int128) (x - cost_price) * sale_x.num * target_sale.den
            - (__int128) (target_price - cost_price) * target_sale.num * sale_x.den;

        i64 a = (i64) a128;
        i64 b = (i64) b128;

        if (a == 0) {
            // 这时不等式退化成 0 > b。
            // 若不成立，说明无论怎么调税收/补贴，目标价都无法严格更优。
            if (!(0 > b)) {
                cout << "NO SOLUTION\n";
                return 0;
            }
            continue;
        }

        if (a > 0) {
            // k > b / a，所以 k >= floor(b / a) + 1
            low = max(low, floor_div(b, a) + 1);
        }
        else {
            // k < b / a。
            // 由于 a < 0，改写成 k * (-a) < (-b)，其中 (-a) > 0。
            // 对整数来说，等价于：
            // k <= ceil((-b) / (-a)) - 1
            high = min(high, ceil_div(-b, -a) - 1);
        }
    }

    if (low > high) {
        cout << "NO SOLUTION\n";
        return 0;
    }

    // 在整数区间 [low, high] 中找绝对值最小的 k。
    i64 answer;
    if (low <= 0 && 0 <= high) {
        answer = 0;
    }
    else if (high < 0) {
        answer = high;
    }
    else {
        answer = low;
    }

    cout << answer << '\n';

    return 0;
}

复杂度

设给出的已知点数量为 m，可行整数售价数量为 P
求每个售价的限制时，需要沿分段函数找到它落在哪一段
总复杂度约为 $O(P * m)$
空间复杂度 $O(m)$

总结

这题最容易出错的不是复杂度，而是下面几个细节：

补贴要加到单位利润里
税收要从单位利润里减掉
目标价必须严格优于其他所有售价，不能并列
相邻已知点之间的销量是线性插值
最后一个点之后如果无论怎么调都无法让目标价最优，要输出 NO SOLUTION

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

题目背景

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

对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）

题目描述

你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。

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

输入格式

输入的第一行为政府对某种商品的预期价；

第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量；

接下来若干行，每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行 -1 -1 表示所有已知价位及对应的销量输入完毕；

输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输出格式

输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。

如在政府预期价上不能得到最大总利润，则输出 NO SOLUTION。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

数据范围及约定

保证输入的所有数字均小于 $10^5$ 。

样例解释（2023/6/22 更新）

如下图所示是输入样例所对应的价格变化图，横轴表示销售价格，纵轴表示销量。

根据题意， $28$ 元是商品的成本。销售价格不应该低于 $28$ 元；当销售价格大于给出的价格的最大值 $31$ 元后，按照售价每提高一元，销量降低 $15$ 计算，例如当售价为 $33$ 元时，销量为 $110-15\times (33-31)=80$ 。在给出来的价位之间，销量呈线性变化。

当政府给该商品补贴 $4$ 元后，企业将该商品定价为 $31$ 元时，取得的利润为 $31-28+4=7$ 元，销量为 $110$ 件，总利润为 $7\times 110=770$ 元，是企业在所有定价下能够取得的最大的总利润。此时企业的售价为政府的期望售价，因此是一个合法方案。

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

目录

题意

思路

一个小表格

代码

复杂度

总结