题目背景

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

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

题目描述

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

总利润=单位商品利润 × × 销量

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

输入格式

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

输出格式

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

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

输入输出样例

输入 #1

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

输出 #1

4

说明/提示

所有数字均小于100000

解题思路：

tips：说实话，这个题目看了很久。。。

最后，发现所求的是什么了。是要求政府给定一个预期的价格，然后你去尝试不同的补贴或者税收，得到他们的利润，并看看在每种税收或补贴下总利润最高的价格是不是政府预期价 。（可以好好思考一下这句，那么我们就计算出不同补贴或税收下，利润最大的价格，再比较）

（最后，好像没有不符合条件的，所以不用管。。。）

那么：

1. 我们可以先将购买者的价格和所对应的销量全部存起来，但这又有两个问题：

   1）在题目给出的价格和销量之间，销量是随价格线性变化的，我们可通过计算得出期间的对应价格与销量，并都储存起来。（具体实施方法见代码）即 价格-销量表。

   2）再输入的最后给定了之后的销量减少值，我们就可以从中得到其后，一直到销量小于0的对应关系，并储存起来。

2. 最后再根据不同的补贴（税收）（用一个循环从1开始跑到10000）依次计算其最大利润，并比较在该最大利润的价格是否与政府的价格相同。

代码：

//代码来源：https://www.luogu.com.cn/user/174034
#include<bits/stdc++.h>
using namespace std;
int a[100010][3];//用于存放价格和销量的数组
int main()
{
    int i=1,j=1,k,expect,down,max,temp,cha,xl,num,s,price,p;
    cin>>expect;//读入预期价
    while(cin>>a[i][1]>>a[i][2]&&a[i][1]!=-1&&a[i] [2]!=-1)//如果输入的两个数不是-1，-1
    {
        i++;//循环变量i++
        if(i>2&&a[i-1][1]-a[i-2][1]>1)//如果两个价格之间差大于一
        {
            i--;//回到上一个读入的销量
            cha=(a[i-1][2]-a[i][2])/(a[i][1]-a[i-1][1]);//求出每次销量减少多少：销量差/价格差
            temp=a[i][1];//记录下价格
            for(j=a[i-1][1]+1;j<=temp;j++)//按价格递增顺序依次写入
            {
                a[i][1]=j;//写入价格
                a[i][2]=a[i-1][2]-cha;//按销量差写入销量
                i++;
            }
        }
    }
    cin>>down;//输入超过最大价格之后每次销量降低多少
    i--;//因为上面的while循环最后有i++所以用i--抵消……
    xl=a[i][2];//记录目前的销量
    while(xl>0)
    {
        if(xl-down<0)break;//如销量小于零则退出
        else//否则
        {
            xl-=down;//销量每次减掉down
            i++;//循环变量++
            a[i][1]=a[i-1][1]+1;//每次价格+1
            a[i][2]=xl;//销量就是xl
        }
    }
    for(j=1;j<=10000;j++)//该遍历了，因为收税相当于补贴*-1所以记录一下符号即可
    {
        max=-99999;//用于存储最大的总利润
        for(k=1;k<=i;k++)//每次扫一遍每一种价格
        {
            num=(a[k][1]-a[1][1]+j)*a[k][2];//套公式算出总利润
            if(num>=max)//如果总利润比目前最大的大
            {
                max=num;//更新max
                price=a[k][1];//记录下价格
                p=1;//记录下符号
            }
        }
        if(price==expect){cout<<j*p;return 0;}//如果价格就是政府预期价则打印出来，因为本身就是从小到大遍历所以不用求绝对值最小的
        max=-99999;//后面是收税，原理同上
        for(k=1;k<=i;k++)
        {
            num=(a[k][1]-a[1][1]-j)*a[k][2];
            if(num>=max)
            {
               max=num;
                price=a[k][1];  
                p=-1;
            }
        }
        if(price==expect){cout<<j*p;return 0;}
    }
    return 0;
}