【題目鏈接】

ybt 1911：【00NOIP普及組】稅收與補貼問題
洛谷 P1023 [NOIP2000 普及組] 稅收與補貼問題

【題目考點】

1. 枚舉

2. 數學

3. 二分查找

【解題思路】

有一點社會經濟常識，才更容易理解這一題。
對一個商品來說，價格越低，銷量越高。價格越高，銷量越低。為了讓利潤最大，商家會找到一個特定價格，在這一價格下，總利潤是最大的(總利潤=(價格-成本)*銷量)。這是市場行為。
然而政府為了民生考慮，必須穩定物價。若是給每件商品補貼，相當于降低每件商品的成本，低價大量出售可以獲得更高利潤。若是給每件商品收稅，相當于抬高商品成本，再低價就虧本了，高價少量出售可以獲得更高利潤。因此政府可以通過補貼或收稅的方式來調整物價。

根據輸入數據，進行插值，得出在無補貼情況下，商人在每個價位可以獲得的最大利潤。
由于低價情況下銷量比高價情況下銷量大，那么低價情況受補貼或稅收的影響也比高價情況大。
不同操作下，不同價位利潤變化規律如下：

操作價位利潤變化該價位下利潤相對預期價利潤的變化

補貼	低于預期價	增加（多）	增加
補貼	預期價	增加（中）	不變
補貼	高于預期價	增加（少）	減少
收稅	低于預期價	減少（多）	減少
收稅	預期價	減少（中）	不變
收稅	高于預期價	減少（少）	增加

在預期價位，有預期價下的利潤，簡稱預期價利潤。
價格低于預期價（在預期價左側）的情況中，利潤最大時利潤為左側最大利潤，簡稱左側利潤。
價格高于預期價（在預期價右側）的情況中，利潤最大時的利潤為右側最大利潤，簡稱右側利潤。
輸入數據后，面對的是以下四種情況之一：

如果左側利潤和右側利潤都小于等于預期價利潤，此時滿足題目要求，輸出補貼或收稅值。

如果左側利潤和右側利潤都大于等于預期價利潤，加稅使右側利潤相對更大，補貼使左側利潤相對更大，無論如何操作都不可能讓預期價下利潤最大，輸出NO SOLUTION。

如果左側利潤高于預期價利潤，且預期價利潤大于等于右側利潤，為了讓預期價利潤為最大值，那么應該相對預期價利潤減少左側利潤，應該收稅。此時問題為應該收多少稅，通過二分查找找到應該收稅的最小值。
收稅值范圍為$1～10^5$，如果右側利潤高于預期價利潤，或左右側利潤都小于等于預期價利潤，此時取二分左側部分（減少征稅），如果不滿足，取二分右側部分（增加征稅）。記錄可以使左右側利潤都小于等于預期價利潤的最小收稅值。

如果右側利潤高于預期價利潤，且預期價利潤高于左側利潤，為了讓預期價利潤為最大值，那么應該相對預期價利潤減少右側利潤，應該補貼。此時問題為應該補貼多少，通過二分查找得到應該補貼的最小值。
補貼值范圍為$1～10^5$，如果左側利潤高于預期價利潤，或左右側利潤都小于等于預期價利潤，此時取二分左側部分（減少補貼），如果不滿足，取二分右側部分（增加補貼）。記錄可以使左右側利潤都小于等于預期價利潤的最小補貼值。

【注】本題數據比較水，不用二分，用枚舉也能過。本文后面給出了幾組測試數據，測試了一些極端情況，必須使用二分才能過。

【題解代碼】

解法1：二分

#include<bits/stdc++.h> using namespace std; #define N 100005 #define INF 0x3f3f3f3f long long num[N], pro[N], tpro[N];//num[i]:價格為i時的銷量 pro[i]:價格為i時的利潤 tpro:臨時表示利潤的數組 int maxIndex(long long arr[], int st, int ed)//求arr下標從st到ed中值最大的元素的下標 {int mxi = st;for(int i = st; i <= ed; ++i){if(arr[i] > arr[mxi])mxi = i;}return mxi; } int main() {int tp, lp, p, dec, part, cp, ep, pl, pr, left, right, mid, minAns;//tp:目標價格 lp:上一次的價格 dec:超過最大價格后銷量下降速率 cin >> tp;//目標價格 //構造數組num，確定無補貼或征稅情況下每個價格對應的銷量 cin >> cp;//成本價 cin >> num[cp];//num[i]:價格為i時的銷量lp = cp;while(true){cin >> p;//價格cin >> num[p];//銷量if(p == -1 && num[p] == -1)break; part = (num[lp]-num[p])/(p-lp);//將num[lp]-num[p]這段數字分成p-lp份，每份為part for(int i = lp+1; i < p; ++i)//插值num[i] = num[i-1] - part;lp = p; }cin >> dec;//價格每增長1元銷量下降值 while(num[lp] > 0)//銷量大于0的情況都列舉出來 {lp++;num[lp] = num[lp-1] - dec;}//跳出循環時，num[lp] <= 0，這一項不要，取第lp-1項為最后一項 ep = lp-1;//ep是最高可用的價格 num可用下標范圍：cp~ep//構造利潤數組，求預期價兩側最大利潤價位 for(int i = cp; i <= ep; ++i)//求利潤數組pro pro[i] = (i - cp) * num[i];//i的利潤：價格減成本乘個數 pl = maxIndex(pro, cp, tp);//pl:左側利潤最大的價位，候選價位包含tp pr = maxIndex(pro, tp, ep);//pr:右側利潤最大的價位 ，候選價位包含tp。如果tp就是最后一個價位ep，那么這樣取出的pr就是tp。 if(pro[pl] <= pro[tp] && pro[tp] >= pro[pr]){//預期價利潤不小于左右側最高利潤，已經滿足條件 不需要征稅或補貼 cout << 0;}else if(pro[pl] > pro[tp] && pro[tp] < pro[pr]){//預期價利潤小于左右側最高利潤，無論如何補貼或征稅都無法讓預期價利潤最大 cout << "NO SOLUTION";}else if(pro[pl] > pro[tp] && pro[tp] >= pro[pr]){//如果左側最大利潤高于預期價利潤，二分查找找到應該收稅的最小值 這里征稅值用正數表示 left = 0, right = 100000, minAns = INF;while(left <= right){mid = (left + right) / 2;for(int i = cp; i <= ep; ++i)//設臨時表示利潤的數組tpro tpro[i] = pro[i]-num[i]*mid;//tpro[i]：價格i加mid稅后的利潤 。num[i]達到5位數 mid達到5位數，二者相乘超過int范圍。所以幾個數組要設為long long pl = maxIndex(tpro, cp, tp);//pl:左側利潤最大的價位 包含tp pr = maxIndex(tpro, tp, ep);;//pr:右側利潤最大的價位 包含tp if(tpro[tp] < tpro[pr])//需要減少收稅，取左半部分 right = mid - 1;else if(tpro[pl] > tpro[tp])//需要加稅，取右半部分 left = mid + 1; else if(tpro[pl] <= tpro[tp] && tpro[tp] >= tpro[pr])//如果滿足條件，看看更少的稅下有沒有滿足條件的情況 {right = mid - 1;minAns = min(minAns, mid);}}if(minAns == INF)//如果沒找到 cout << "NO SOLUTION";elsecout << -minAns;//輸出收稅時，加負號 }else if(pro[pl] <= pro[tp] && pro[tp] < pro[pr]){//如果右側最大利潤高于預期價利潤，二分查找找到應該補貼的最小值 這里補貼值用正數表示 left = 0, right = 100000, minAns = INF;while(left <= right){mid = (left + right) / 2;for(int i = cp; i <= ep; ++i)//設臨時表示利潤的數組tpro tpro[i] = pro[i]+num[i]*mid;//tpro[i]：價格i加mid補貼后的利潤 pl = maxIndex(tpro, cp, tp);//pl:左側利潤最大的價位 pr = maxIndex(tpro, tp, ep);;//pr:右側利潤最大的價位 if(tpro[tp] < tpro[pr])//需要增加補貼，取右半部分 left = mid + 1;else if(tpro[pl] > tpro[tp])//需要減少補貼，取左半部分 right = mid - 1; else if(tpro[pl] <= tpro[tp] && tpro[tp] >= tpro[pr]){//如果滿足條件，看看更少的補貼下有沒有滿足條件的情況 right = mid - 1;minAns = min(minAns, mid);}}if(minAns == INF)//如果沒找到 cout << "NO SOLUTION";elsecout << minAns;}return 0; }

附:【更多測試數據】

• 測試左右側最大利潤高于預期價利潤

31 28 130 30 30 31 18 -1 -1 1

輸出：NO SOLUTION

• 測試左低右高，在補貼或收稅變化1后，直接變為左高右低的情況

11 10 80 11 35 12 20 -1 -1 20

輸出：NO SOLUTION

• 測試

程序復雜度：$O(n^2)$復雜度的算法都過不了。

測試變量范圍：一些量不設成long long過不了。

將預期價設為價格列表最后一項時的情況。

100000 1 100000 100000 1 -1 -1 1

輸出：-99997

總結

以上是生活随笔為你收集整理的信息学奥赛一本通 1911：【00NOIP普及组】税收与补贴问题 | 洛谷 P1023 [NOIP2000 普及组] 税收与补贴问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。