NOI分区联赛 - 2000年第六届普及组试题解析

注意：解析和源程序均为OIBH站长刘汝佳所写，疏漏在所难免，但至少程序均通过了比赛时使用的测试数据，
所以还是可以一看。

第一题：     源程序
比较简单。为了让程序编写时思路清晰和利于调试，可以采取如下的方法：
等号两边分别处理，每次读一个“项”(先读符号，系数，再看是否有为一次项)，把方程简化成：
ax+b=cx+d (假设x为未知数，a,b,c,d为系数)
则x=(d-b)/(a-c)
注意没有系数的情况，如：a和1a是等价的。大家注意看我的程序是如何处理的。
程序见附件。

第二题：     源程序
我先来说说题目的意思。就从样例开始分析。
输入是：
31
28 130
30 120
31 110
-1 -1
15

意思就是政府预期价是31元。成本28元，按成本销售的时候可以买130件产品。
每个卖30元的时候可以卖120个，
每个卖31元(输入的最高价位)的时候可以卖110个，
每个卖32元的时候可以卖：110-15=95个。
每个卖33元的时候可以卖：110-15-15=80个。
每个卖34元的时候可以卖：110-15-15-15=65个。
...
因为“相邻价位之间的销量变化是均匀的”，因此28元卖130个,30元卖120个就可以知道
29元卖125个(平均每元减少的销量是(130-120) div (30-28)=5)

输出是4，我们来解释一下为什么是4。
4代表补贴是4元，所以:
在卖28元的时候，总利润是：(28-28+4)*130=520元，
在卖29元的时候，总利润是：(29-28+4)*125=625元，
在卖30元的时候，总利润是：(30-28+4)*120=720元，
在卖31元的时候，总利润是：(31-28+4)*110=770元，
在卖32元的时候，总利润是：(32-28+4)*95=760元，
...
在卖38元的时候，总利润是：(38-28+4)*5=70元，
显然可能的价位就是28~38了。(不能低于成本，卖39的时候销售量就是负数了)

可以看出，现在卖31元最划算，所以人们都愿意卖31元，这样一来不就达到政府的目的了吗！！
而当补贴是0,1,2,3的时候卖31元并不是最划算的，政府的目的达不到，你当然就没有分啦！

题意清楚了吗？好，下面分析思路。
穷举显然可以，但是没有什么意思，留给大家自己写。下面讲我的另外一种算法，数学味道要浓一些，
希望大家坚持看完。

由于需要N元钱最划算，相当于使N元钱的利润大于等于每种价格的利润。因此可以分别考虑。
设补贴为x，则N元钱的利润是：(p为成本)
(N-p+x)*d[N]=(N-p)*d[N]+x*d[N]

因此N元钱比M元钱划算的时候有：
(N-p)*d[N]+x*d[N]>=(M-p)*d[M]+x*d[M],即：
x(d[N]-d[M])>=M*d[M]-N*d[N]-p*(d[M]-d[N])

这样，要使N元钱比M元钱划算，x必须在区间[k1,k2] (k1,k2根据上面的式子得出)

例如上面的例子：
31元比28元划算时有：
(31-28+x)*110>=(28-28+x)*130
即：330+110x>=130x,故x<=16.5

31元比30元划算时有：
330+110x>=240+120x,故x<=9

31元比32元划算时有：
330+110x>=380+95x,故x>=3.33
...
最后所有式子取交集，就得到了x的范围。要求绝对值最小值还不容易吗？ :-P
大家注意我在求出了k1,k2后做的最后的处理。可能有一边或两边无界的情况。
正数和负数的处理也有区别。

有一点需要注意：题目没有说输入价位是从小到大排序好的，虽然测试数据都是排序好的。
我就偷个懒如何？:-P

程序见附件。

第三题：
同提高组第二题,参见提高组试题解析。

第四题：
同提高组第三题,参见提高组试题解析。