题目背景

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

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

题目描述

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

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

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

输入格式

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

输出格式

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

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

输入输出样例

输入 #1 复制

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

输出 #1 复制

4

说明/提示

所有数字均小于\(100000\)

思路

首先，这道题的题目实在有点难理解，以样例为例，先体会一下。

1. 输入预期价31
2. 输入成本和销售量28 130
3. 输入30 120
4. 补全29 125
5. 输入31 110
6. 补全30 117
7. 输入-1 -1
8. 输入15
9. 接着补全32 95，33 80以此类推

这样你就有一张全价位的表了。
接着，因为要在预期价上得到最大的利润，所以，在其他任何价位上的利润都不能超过它。
设当前来到了 \(i\) 元的价位上，政府要补贴 \(x\) 元（如果 \(x\) 为负，则是收税）
就可以列出方程

(i-chengben+x)*c[i]≤(yuqijia-chengben+x)*c[yuqijia]

然后，用一个代数式表示 \(x\) :

\(x=\dfrac {(i-chengben)\times c_i-(yuqijia-chengben)\times c_{yuqijia}}{c_{yuqijia}-c_i}\)

或者

\(x=\dfrac {(yuqijia-chengben)\times c_{yuqijia}-(i-chengben)\times c_i}{c_i-c_{yuqijia}}\)
最后，只要枚举 \(i\) ，更新 \(maxx\) 和 \(minx\) ，再根据 \(maxx\) 和 \(minx\) 输出

代码

#include<bits/stdc++.h>
#define maxn 100039
using namespace std;
int yuqijia,chengben,x,y,p,c[maxn];
double minx=-1e9,maxx=1e9;
int main()
{
    cin>>yuqijia>>x>>y;
	chengben=x;
    while(x!=-1&&y!=-1)
    {
        c[x]=y;
        if(x!=chengben)
        for(int i=p+1;i<=x-1;i++)
            c[i]=c[i-1]+(c[x]-c[p])/(x-p);
        p=x;
        cin>>x>>y;
    }
	cin>>x;
    while(c[p]>x){
        p++;
		c[p]=c[p-1]-x;
	}
    for(int i=chengben;i<=p;i++)
    {
    	if(i==yuqijia)continue;
        double ans=double(c[yuqijia]*(yuqijia-chengben)-c[i]*(i-chengben))/(c[i]-c[yuqijia]);
        //套公式
        if(c[i]>c[yuqijia])maxx=min(maxx,ans);
        else minx=max(minx,ans);
    }
    if(minx>0)
		printf("%d",(int)ceil(minx));
    else if(maxx<0)
	    printf("%d",(int)floor(maxx));
    else if(minx<=maxx)
		printf("0");
	else
	    printf("NO SOLUTION");
    return 0;
}

谢谢--zhengjun