🏆今日学习目标：
🍀学习了解P1023 [NOIP2000 普及组] 税收与补贴问题
✅创作者：贤鱼
⏰预计时间：15分钟

题目

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

题目背景

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

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

题目描述

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

总利润=单位商品利润 $ \times $ 销量

单位商品利润=单位商品价格 - 单位商品成本 （- 税金 or + 补贴）

输入格式

输入的第一行为政府对某种商品的预期价，第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量，以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行 -1 -1 表示所有已知价位及对应的销量输入完毕，输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输出格式

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

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

样例 #1

样例输入 #1

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

样例输出 #1

4

提示

所有数字均小于 $10^5$

思路

这个题主要解决的有一下三个方面

不改价格的情况下找找符合题目要求的数据
补贴下找到符合题目要求的数据
税收下找到符合题目要求的数据

所以这个题的思路非常明确

由于是线性数据，第一个一定是最小，最后一个一定是最大

我们要算出数据的斜率来算出每个销售量下的售价才能找到题目要求的数据
如果用k记录斜率
xjg是上一个的价格，jg是现在的价格，xs是现在的售价，xxs是上一个的售价

那么斜率k[xjg]=(xs-xxs)/(jg-xjg);

斜率出来了后面的算出每一个销售量下的售价也就好算了
用num[i]储存i销售量下的价格
那么如果num此时为空
这里的xk就为斜率，xxjg等于当前价格，nm等于i销售量下的售价

num[i]=xk*(i-xxjg)+nm;

到此为止，我们需要的数据都算完了，接下来按照题目要求寻找答案就可以了

AC代码

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int mb,ans,jg,xs;
double k[1010101],num[1010101];
int main(){
    cin>>mb;
    cin>>jg>>xs;
    int minj=jg;
    int xjg,xxs;//这里先储存一下最小的价格和销售量
    while(jg!=-1&&xs!=-1){
        xjg=jg,xxs=xs;
        num[jg]=xs;//由于最后一位输入-1，所以这里就可以储存最大的售价和对应销售量
        cin>>jg>>xs;
        k[xjg]=(xs-xxs)/(jg-xjg);//这里计算斜率
    }
    int yd;
    cin>>yd;
    int xk;
    int xxjg;
    int nm;
    for(int i=minj;i<=xjg;i++){
        if(!num[i]){
            num[i]=xk*(i-xxjg)+nm;
        }else{
            xk=k[i];
            xxjg=i;
            nm=num[i];
        }
    }
    int max=-1;
    while(xxs-yd>0) xjg++,xxs-=yd,num[xjg]=xxs;//处理一下比最大售价还大的售价对应的销售量
    for(int i=minj;i<=xjg;i++){//首先先看看没有修改价格的最大利润
        if((i-minj)*num[i]>max) ans=i,max=(i-minj)*num[i];
    }
    if(ans==mb){//符合题意直接输出
        cout<<0;
        return 0;
    }
    if(ans>mb){//如果不改价格的数据和要求不同，按照要求处理
        for(int i=1;i>=0;i++){//这一层代表修改的价格
            ans=0,max=-1;
            for(int j=minj;j<=xjg;j++)//从最小价格到最大价格
            if((j-minj+i)*num[j]>=max){//这里按照题目要求处理就可以了
                ans=j;
                max=(j-minj+i)*num[j];
            }
            if(ans==mb){
                cout<<i;
                return 0;
            }
        }
    }else{
    for(int i=-1;i<=0;i--){//这里让i--，实现了降低价格的作用![请添加图片描述](https://ucc.alicdn.com/images/user-upload-01/8b448e31e8934743ba23d3593036cb57.gif)

            ans=0,max=-1;
            for(int j=minj+1;j<=xjg;j++)//和上面同理
            if((j-minj+i)*num[j]>=max){
                ans=j;
                max=(j-minj+i)*num[j];
            }
            if(ans==mb){
                cout<<i;
                return 0;
            }
        }

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