CSP历年复赛题-P1023 [NOIP2000 普及组] 税收与补贴问题

原题链接：https://www.luogu.com.cn/problem/P1023

题意解读：给定商品单价和对应销量表，计算使得采用预期价格销售得到最大利润时的最小补贴或者税收。

解题思路：

1、样例模拟

31
28 130
30 120
31 110
-1  -1
15

政府预期价格：31

商品成本：28，按成本价售卖销量：130

商品单价：30，对应销量：120

商品单价：31：对应销量：110

超出商品最高单价31后，每增加一元，销量降低15

要计算预期价带来的总利润是否最大，就要和所有价格带来的总利润进行比较，因此需要将商品单价从28以上销量不为0的数据都补充完整

比如：28和30元之间有29元，根据销量是线性的得知29元的销量是130 - (130 - 120) / 2 = 125

然后针对31元以上的销量每增加一元减少15进行补充，最终得到单价-销量表：

28 130
29 125
30 120
31 110
32 95
33 80
34 65
35 50
36 35
37 20
38 5

 再分别枚举补贴和税收，补贴从1~100000，税收从-1到-100000

如果找到一个补贴，使得按照预期价格销售的总利润最大，则记录补贴值

如果找到一个税收，使得按照预期价格销售的总利润最大，则记录税收值

最后根据补贴和税收的值，输出绝对值较小的

2、算法总结

第一步：构建一个价格-销量表，价格从成本价以上，每增加1都有对应的销量，销量大于0

第二步：枚举补贴，计算使得按照预期价格销售的总利润最大的第一个补贴值

第三步：枚举税收，计算使得按照预期价格销售的总利润最大的第一个税收值

第四步：输出结果

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

int t; //政府预期价
int s, ss; //成本价，成本价的销量
int p[N]; //价格-销量表，单价对应的销量
int d; //最高单价外每升高一块钱将减少的销量

int main()
{
    cin >> t >> s >> ss;
    int x, y; 
    int lastx = s, lasty = ss; //上一个单价、销量
    int maxp; //最大单价

    p[s] = ss;
    while(cin >> x >> y)
    {
        if(x == -1 && y == -1) break;
        maxp = max(maxp, x); //记录最大单价
        p[x] = y;
        int change = (lasty - y) / (x - lastx); //计算单价lastx到x之间单价每增加1，销量变化值
        for(int i = lastx + 1, j = 1; i < x; i++, j++)
        {
            p[i] = lasty - change * j;
        }
        lastx = x, lasty = y;
    }
    cin >> d;
    
    //补齐超出最大单价的销量
    for(int i = 1; p[maxp] - d * i > 0; i++)
    {
        p[maxp + i] = p[maxp] - d * i;
    }

    //枚举补贴，1~100000
    int a = INT_MAX;
    for(int bt = 1; bt <= 100000; bt++)
    {   
        int yuqi = (t - s + bt) * p[t]; //政府预期价格的利润
        int maxs = 0; //最大利润
        for(int i = s; p[i] > 0; i++)
        {
            maxs = max(maxs, (i - s + bt) * p[i]);
        }
        if(yuqi == maxs)
        {
            a = bt;
            break;
        }
    }

    //枚举税收，-1~-100000
    int b = INT_MAX;
    for(int tax = -1; tax >= -100000; tax--)
    {   
        int yuqi = (t - s + tax) * p[t]; //政府预期价格的利润
        int maxs = 0; //最大利润
        for(int i = s; p[i] > 0; i++)
        {
            maxs = max(maxs, (i - s + tax) * p[i]);
        }
        if(yuqi == maxs)
        {
            b = tax;
            break;
        }
    }
    
    if(a == INT_MAX & b == INT_MAX) cout << "NO SOLUTION";
    else
    {
        if(abs(a) < abs(b)) cout << a;
        else cout << b;
    }
    return 0;
}