P1023 税收与补贴问题
网页链接
P1023 税收与补贴问题
题目背景
每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）
对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）
题目描述
你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。
- 总利润= ==单位商品利润× \times×销量
- 单位商品利润= ==单位商品价格− -−单位商品成本（减去税金 或者 加上补贴）
输入格式
输入的第一行为政府对某种商品的预期价；
第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销售量；
接下来若干行，每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行-1 -1表示所有已知价位及对应的销量输入完毕；
输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。
输出格式
输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。
如在政府预期价上不能得到最大总利润，则输出NO SOLUTION。
输入输出样例 #1
输入 #1
31 28 130 30 120 31 110 -1 -1 15输出 #1
4说明/提示
数据范围及约定
保证输入的所有数字均小于10 5 10^5105。
样例解释（2023/6/22 更新）
如下图所示是输入样例所对应的价格变化图，横轴表示销售价格，纵轴表示销量。
根据题意，28 2828元是商品的成本。销售价格不应该低于28 2828元；当销售价格大于给出的价格的最大值31 3131元后，按照售价每提高一元，销量降低15 1515计算，例如当售价为33 3333元时，销量为110 − 15 × ( 33 − 31 ) = 80 110-15\times (33-31)=80110−15×(33−31)=80。在给出来的价位之间，销量呈线性变化。
当政府给该商品补贴4 44元后，企业将该商品定价为31 3131元时，取得的利润为31 − 28 + 4 = 7 31-28+4=731−28+4=7元，销量为110 110110件，总利润为7 × 110 = 770 7\times 110=7707×110=770元，是企业在所有定价下能够取得的最大的总利润。此时企业的售价为政府的期望售价，因此是一个合法方案。
解题思路
本题核心是通过线性插值补全销量+枚举税收/补贴金额求解最优解：首先读取预期价格、成本、初始销量及各价位销量，用线性插值补全已知价位间的销量，按固定递减率补全最高价位后的销量；计算无税收/补贴时的最大利润价位，若为预期价则输出0；若最大利润价高于预期价，枚举正补贴金额，直到预期价成为唯一最大利润价；若低于则枚举负税收金额（绝对值递增），直到预期价最优。利润计算公式为（单价-成本±金额）×销量，需找到使预期价利润最大的最小金额，若无法让预期价成为最优则输出NO SOLUTION。该方法通过插值补全数据，枚举适配金额，精准满足题目要求。
总结
- 核心逻辑：补全所有价位的销量数据，枚举税收/补贴金额，使预期价的利润为所有价位中最大。
- 关键操作：线性插值补全已知价位间销量，按递减率补全高价区销量，枚举金额验证预期价最优性。
- 效率保障：销量补全为线性复杂度，金额枚举范围有限，适配输入数据规模（数值<1e5）。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vt;typedefpair<ll,ll>pll;constll N=1e5+10;constll mod=1e9+7;constll INF=1e18;doublek[N],num[N];intmain(){ll ex,c,n;cin>>ex>>c>>n;ll pc=c;ll lc,ln;while(c!=-1&&n!=-1){lc=c,ln=n,num[c]=n;cin>>c>>n;k[lc]=(n-ln)/(c-lc);//计算斜率}ll cnt=0,cc=0,kk=0,nn=0;cin>>cnt;for(ll i=pc;i<=lc;++i){if(!num[i])num[i]=kk*(i-cc)+nn;elsekk=k[i],cc=i,nn=num[i];}ll ans,mx=0;while(ln-cnt>0)lc++,ln-=cnt,num[lc]=ln;for(ll i=pc;i<=lc;++i){if((i-pc)*num[i]>mx)ans=i,mx=(i-pc)*num[i];}if(ans==ex)puts("0");elseif(ans>ex){for(ll x=1;;x++){mx=ans=0;for(ll i=pc;i<=lc;++i){if((i-pc+x)*num[i]>=mx)ans=i,mx=(i-pc+x)*num[i];}if(ans==ex){cout<<x<<endl;return0;}}}else{for(ll x=-1;;x--){mx=ans=0;for(ll i=pc+1;i<=lc;++i){if((i-pc+x)*num[i]>=mx)ans=i,mx=(i-pc+x)*num[i];}if(ans==ex){cout<<x<<endl;return0;}}}}
