首页 > 代码库 > 1023税收与补贴问题
1023税收与补贴问题
题意：2000Noip提高组
分析：这题没有理解好题意，最后看了题解之后才做出来的，下面贴一下刘汝佳大神的题解
我先来说说题目的意思。就从样例开始分析。
输入是：
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后做的最后的处理。可能有一边或两边无界的情况。
正数和负数的处理也有区别。
有一点需要注意：题目没有说输入价位是从小到大排序好的，虽然测试数据都是排序好的。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <string> 5 #include <vector> 6 #include <algorithm> 7 #include <set> 8 #include <map> 9 #include <bitset>10 #include <cmath>11 #include <queue>12 #include <stack>13 using namespace std;14 const int maxn=10010;15 const int INF=1<<30;16 int price[maxn],sell[maxn],d[maxn]; //价格和销量17 int n,p; //达到最大利润的售价和成本18 int num; //达到最大利润之后的减少量19 int main()20 {21 while(cin>>n)22 {23 int k=0;24 while(true){ //已知的售价和销量25 int x,y;26 cin>>x>>y;27 if(x==-1&&y==-1) break;28 ++k;29 price[k]=x;30 sell[k]=y;31 }32 cin>>num;33 34 int p=price[1]; //成本35 int most=price[k]+sell[k]/num; //最高售价36 if((n<p)||(n>most)){37 cout<<"NO SOLUtION"<<endl;38 continue;39 }40 memset(d,0,sizeof(d));41 42 //处理销量43 for(int i=1;i<=k-1;i++){44 int tt=(sell[i]-sell[i+1])/(price[i+1]-price[i]);45 for(int j=price[i];j<=price[i+1]-1;j++)46 d[j]=sell[i]-tt*(j-price[i]);47 }48 for(int i=price[k];i<=most;i++)49 d[i]=sell[k]-num*(i-price[k]);50 51 //cout<<"456"<<endl;52 double k1=-INF,k2=INF;53 for(int i=p;i<=most;i++){54 int r=d[n]-d[i];55 int ans=i*d[i]-n*d[n]-p*(d[i]-d[n]);56 if(r>0&&k1<(double)ans/(double)r)57 k1=(double)ans/(double)r;58 if(r<0&&k2>(double)ans/(double)r)59 k2=(double)ans/(double)r;60 }61 62 int u1,u2;63 if(k1==-INF) u1=-INF;64 else if(k1>0&&(k1-(int)k1>0)) u1=(int)k1+1;65 else u1=k1;66 if(k2==INF) u2=INF;67 else if(k2<0&&((int)k2-k2>0)) u2=(int)k2-1;68 else u2=k2;69 70 if(u1<0&&u2>0){71 u1=0,u2=0;72 }73 if(u1>u2) cout<<"NO SOLUTION"<<endl;74 else if(abs(u1)<abs(u2)) cout<<u1<<endl;75 else cout<<u2<<endl;76 }77 return 0;78 }
1023税收与补贴问题