P1023 税收与补贴问题【洛谷算法习题】

P1023 税收与补贴问题网页链接P1023 税收与补贴问题题目背景每样商品的价格越低其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量产品不会低于成本销售并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后销量以某固定数值递减。我们假设价格及销售量都是整数对于某些特殊商品不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币题目描述你是某家咨询公司的项目经理现在你已经知道政府对某种商品的预期价格以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额也为整数才能使商家在这样一种政府预期的价格上获取相对其他价位上的最大总利润。总利润 单位商品利润× \times×销量单位商品利润 单位商品价格− -−单位商品成本减去税金 或者 加上补贴输入格式输入的第一行为政府对某种商品的预期价第二行有两个整数第一个整数为商品成本第二个整数为以成本价销售时的销售量接下来若干行每行都有两个整数第一个为某价位时的单价第二个为此时的销量以一行-1 -1表示所有已知价位及对应的销量输入完毕输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。输出格式输出有两种情况若在政府预期价上能得到最大总利润则输出一个单独的整数数的正负表示是补贴还是收税数的大小表示补贴或收税的金额最小值。若有多解取绝对值最小的输出。如在政府预期价上不能得到最大总利润则输出NO SOLUTION。输入输出样例 #1输入 #131 28 130 30 120 31 110 -1 -1 15输出 #14说明/提示数据范围及约定保证输入的所有数字均小于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-284731−2847元销量为110 110110件总利润为7 × 110 770 7\times 1107707×110770元是企业在所有定价下能够取得的最大的总利润。此时企业的售价为政府的期望售价因此是一个合法方案。解题思路本题核心是通过线性插值补全销量枚举税收/补贴金额求解最优解首先读取预期价格、成本、初始销量及各价位销量用线性插值补全已知价位间的销量按固定递减率补全最高价位后的销量计算无税收/补贴时的最大利润价位若为预期价则输出0若最大利润价高于预期价枚举正补贴金额直到预期价成为唯一最大利润价若低于则枚举负税收金额绝对值递增直到预期价最优。利润计算公式为单价-成本±金额×销量需找到使预期价利润最大的最小金额若无法让预期价成为最优则输出NO SOLUTION。该方法通过插值补全数据枚举适配金额精准满足题目要求。总结核心逻辑补全所有价位的销量数据枚举税收/补贴金额使预期价的利润为所有价位中最大。关键操作线性插值补全已知价位间销量按递减率补全高价区销量枚举金额验证预期价最优性。效率保障销量补全为线性复杂度金额枚举范围有限适配输入数据规模数值1e5。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e510;constll mod1e97;constll INF1e18;doublek[N],num[N];intmain(){ll ex,c,n;cinexcn;ll pcc;ll lc,ln;while(c!-1n!-1){lcc,lnn,num[c]n;cincn;k[lc](n-ln)/(c-lc);//计算斜率}ll cnt0,cc0,kk0,nn0;cincnt;for(ll ipc;ilc;i){if(!num[i])num[i]kk*(i-cc)nn;elsekkk[i],cci,nnnum[i];}ll ans,mx0;while(ln-cnt0)lc,ln-cnt,num[lc]ln;for(ll ipc;ilc;i){if((i-pc)*num[i]mx)ansi,mx(i-pc)*num[i];}if(ansex)puts(0);elseif(ansex){for(ll x1;;x){mxans0;for(ll ipc;ilc;i){if((i-pcx)*num[i]mx)ansi,mx(i-pcx)*num[i];}if(ansex){coutxendl;return0;}}}else{for(ll x-1;;x--){mxans0;for(ll ipc1;ilc;i){if((i-pcx)*num[i]mx)ansi,mx(i-pcx)*num[i];}if(ansex){coutxendl;return0;}}}}