跳至正文

税收与补贴问题

  • OI路程

我一直以为普及组的题目都非常简单,几天看到这题我错了。读了两天题目,硬是不知道题目讲的是什么,悲哀。。
到网上找到一份不错的结题报告,想自己写,估计没那个水平。直接转上来吧,至于代码,等下我会把C的代码写上(自己写)。

我先来说说题目的意思。就从样例开始分析。
输入是:
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]+xd[N]>=(M-p)d[M]+xd[M],即:
x(d[N]-d[M])>=Md[M]-Nd[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的范围。要求绝对值最小值还不容易吗? 😛
大家注意我在求出了k1,k2后做的最后的处理。可能有一边或两边无界的情况。
正数和负数的处理也有区别。

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


我的程序:

var
 p0,s0,n,d,i,pp,ss,o,tmp:longint;
 p,s:array[-32767..32767]of longint;

begin
 readln(p0);
 n:=1;
 readln(p[1],s[1]);
 readln(pp,ss);
 while ss<>-1 do
 begin
 d:=(ss-s[n])div(pp-p[n]);
 tmp:=p[n];
 for i:=tmp+1 to pp do
 begin
 inc(n);
 p[n]:=p[n-1]+1;
 s[n]:=s[n-1]+d;
 end;
 readln(pp,ss);
 end;
 readln(d);
 while s[n]-d>=0 do
 begin
 inc(n);
 p[n]:=p[n-1]+1;
 s[n]:=s[n-1]-d;
 end;

 for o:=1 to n do if p[o]=p0 then break;
 for i:=0 to 1000000 do
 begin
 if ((p[o]+i-p[1])*s[o]>=(p[o-1]+i-p[1])*s[o-1])and
 ((p[o]+i-p[1])*s[o]>=(p[o+1]+i-p[1])*s[o+1]) then
 begin writeln(i);halt;end;
 if p[o]-i-p[1]>=0 then
 if ((p[o]-i-p[1])*s[o]>=(p[o-1]-i-p[1])*s[o-1])and
 ((p[o]-i-p[1])*s[o]>=(p[o+1]-i-p[1])*s[o+1]) then
 begin writeln(-i);halt;end;
 end;
 writeln(\'NO SOLUTION\');
end.

我的C代码等下再交上来,写死我了,昨晚上从十点写到一十二点半一直都没写出来,今天找CodeWays要了这题的数据才发现问题的所在,总之代码写的太丑了。。。哎,晚点再看看那人写的pascal代码,再修改修改吧。

C语言:

#include <stdio.h>
#include <math.h>
#define add(a, b) do{\\
 goods[count].priece = (a);\\
 goods[count].number = (b);\\
 count++;\\
}while(0)
#define min(a, b) ((a)<(b)?(a):(b))
#define max(a, b) ((a)>(b)?(a):(b))
struct goods{
 int priece;
 int number;
}goods[10000];
int count;
int x, number, cost;

void init(void)
{
 int i;
 int a, b;
 int c, d;
 int k, f;

 scanf(%d, &x);
 scanf(%d%d, &a, &b);
 cost = a;
 x -= cost;
 while(scanf(%d%d, &c, &d), (c != -1 || d != -1)){
 k = (d - b) / (c - a);
 f = d - c * k;
 for(i = a; i <= c - 1; i++){
 add(i - cost, k * i + f);
 }
 a = c, b = d;
 }
 scanf(%d, &k);
 for(i = a; (b - (i - a) * k) > 0; i++){
 add(i - cost, (b - (i - a) * k));
 }
}

int main(void)
{
 int i, j;
 int a, b, k;
 double up = -100000, down = 1000000;
 init();
 for(i = 0; i < count; i++){
 if(goods[i].priece == x){
 number = goods[i].number;
 break;
 }
 }
 for(i = 0; i < count; i++){
 k = 1;
 a = goods[i].priece * goods[i].number - number * x;
 b = number - goods[i].number;
 if(b < 0){
 k = -1;
 }
 if(b != 0){ //排除goods[i].priece == x的情况
 if(k == 1){
 up = max(up, (double)a / b);
 }else{
 down = min(down, (double)a / b);
 }
 }
 }
 if(up <= down){
 if(up > 0){
 printf(%d\\n, (int)ceil(up));
 }else{
 down = fabs(down);
 printf(%d\\n, - (int)ceil(down));
 }
 }else{
 printf(NO SOLUTION\\n);
 }
 return 0;
}

发表回复

您的电子邮箱地址不会被公开。