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

题目背景

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

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

题目描述

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

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

输入格式

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

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

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

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

输出格式

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

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

输入输出样例

输入 #1

>31

>28 130

>30 120

>31 110

>-1 -1

>15

输出 #1

>4

说明/提示

数据范围及约定

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

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

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

根据题意，28 元是商品的成本。销售价格不应该低于28元；当销售价格大于给出的价格的最大值 31 元后，按照售价每提高一元，销量降低15计算，例如当售价为33元时，销量为 110-15×(33—31)＝80 。在给出来的价位之间，销量呈线性变化。 当政府给该商品补贴 4 元后，企业将该商品定价为 31 元时，取得的利润为 31-28＋4＝7 元，销量为 110 件，总利润为 7×110＝770 元，是企业在所有定价下能够取得的最大的总利润。此时企业的售价为政府的期望售价，因此是一个合法方案。

标签

数学，枚举，NOIP普及组，2000年

做题过程&&吐槽

做题比较曲折，抄看了题解，画了图，debug了半个多小时，还WA了一个点

无解情况写在题面上，一个点都不是无解的是什么鬼啊

正常政府哪个会这种管市场啊喂

思考思路

已知这题是数学，枚举，所以我们需要找到一个有限枚举的数据，然后在枚举中求出最值，所以枚举补贴（或者税收）显然是不可取的（虽然能AC）

按照题目给的条件，我们知道一个最基础的事实，即在当前补贴下定价为政府预期价格所得到的利润一定是最大的，以样例为例，可以列出如下式子

$(31-28+x)110>=(28-28+x)130$

>$(31-28+x)110>=(29-28+x)125$

>$(31-28+x)110>=(30-28+x)120$

>$(31-28+x)110>=(32-28+x)95$

>......

以此类推，将其中的具体数据变成未知数

p_0 表示政府预期价格

p_1 表示成本价格

>num_i 表示价格为i时的销量

>t 表示要求的量，即补贴/税收的价格

p_x 表示枚举的每一个可能的价格（最小不小于成本，最大其销量不能为负）

那么根据题目的要求和题面上的公式，可以得到以下不等式

至此，这题的大概思路已经明晰了，但是还有一个要注意的点，就是在销量与单价的关系时若要通过一次函数推出其余的关系其中的斜率 k 可能不为整数，所以其销量对应关系要用小数存，最后还原到整数时记得考虑正负两种情况 （虽然我并不知道自己求了个最大值有什么用）

参考代码

我相信很多人直接拉下来看代码，但是我觉得吧，一道未定级的题目，又是真题，最好还是以自己的思路写一遍比较好

#include<iostream>
#include<cmath>

using namespace std;

typedef pair<int,int> PII;

const int N=2e5+10;
const int inf=0x3f3f3f3f;

int p0,p1,n1,n2,idx,Min=inf,Max=-inf;
double num[N];
PII P[N];

int f()
{
    for(int i=1;i<idx;i++)
    {
        double k=1.0*(P[i+1].second-P[i].second)/(P[i+1].first-P[i].first);
        num[P[i].first]=P[i].second;
        for(int j=P[i].first+1;j<P[i+1].first;j++)
        {
            num[j]=num[j-1]+k;
        }
    }
    int res;
    for(int i=P[idx].second,j=P[idx].first;i>0;i-=n2,j++)
    {
        num[j]=i;
        res=j;
    }
    return res;
}

int f1(int px)
{
    int t=((px*num[px])-(p0*num[p0]))/(num[p0]-num[px])+p1;
    if(t<0)
        return floor(1.0*((px*num[px])-(p0*num[p0]))/(num[p0]-num[px])+p1);
    else
        return ceil(1.0*((px*num[px])-(p0*num[p0]))/(num[p0]-num[px])+p1);
}

void f0(int px)
{
    bool flag=num[p0]<num[px];
    if(flag)
        Min=min(Min,f1(px));
    else
        Max=max(Max,f1(px));
}
int main()
{
    cin>>p0;
    int p,n;
    cin>>p>>n;
    while(p!=-1||n!=-1)
    {
        idx++;
        P[idx]={p,n};
        cin>>p>>n;
    }
    cin>>n2;
    int end=f();
    p1=P[1].first;
    for(int i=p1;i<=end;i++)
    {
        if(i!=p0)
            f0(i);
    }
    if(abs(Min)>abs(Max)||abs(Min)==abs(Max))
        cout<<Max;
    else
        cout<<Min;
    return 0;
}

第一次用内置的 markdown 语法写题解，有点生疏，请谅解

这个王码的markdown格式有点离谱，还是自己的好看

还有这个题解怎么不支持 LateX 语法，大面积用到的我截了个图贴上去，其他地方的$请自行过滤