信息学奥赛一本通 1911：【00NOIP普及组】税收与补贴问题 | 洛谷 P1023 [NOIP2000 普及组] 税收与补贴问题

信息学奥赛一本通 1911：【00NOIP普及组】税收与补贴问题 | 洛谷 P1023 [NOIP2000 普及组] 税收与补贴问题 【题目链接】

ybt 1911：【00NOIP普及组】税收与补贴问题
洛谷 P1023 [NOIP2000 普及组] 税收与补贴问题

【题目考点】 1. 枚举 2. 数学 3. 二分查找 【解题思路】

有一点社会经济常识，才更容易理解这一题。
对一个商品来说，价格越低，销量越高。价格越高，销量越低。为了让利润最大，商家会找到一个特定价格，在这一价格下，总利润是最大的(总利润=(价格-成本)*销量)。这是市场行为。
然而政府为了民生考虑，必须稳定物价。若是给每件商品补贴，相当于降低每件商品的成本，低价大量出售可以获得更高利润。若是给每件商品收税，相当于抬高商品成本，再低价就亏本了，高价少量出售可以获得更高利润。因此政府可以通过补贴或收税的方式来调整物价。

根据输入数据，进行插值，得出在无补贴情况下，商人在每个价位可以获得的最大利润。
由于低价情况下销量比高价情况下销量大，那么低价情况受补贴或税收的影响也比高价情况大。
不同 *** 作下，不同价位利润变化规律如下：

*** 作价位利润变化该价位下利润相对预期价利润的变化补贴低于预期价增加（多）增加补贴预期价增加（中）不变补贴高于预期价增加（少）减少收税低于预期价减少（多）减少收税预期价减少（中）不变收税高于预期价减少（少）增加

在预期价位，有预期价下的利润，简称预期价利润。
价格低于预期价（在预期价左侧）的情况中，利润最大时利润为左侧最大利润，简称左侧利润。
价格高于预期价（在预期价右侧）的情况中，利润最大时的利润为右侧最大利润，简称右侧利润。
输入数据后，面对的是以下四种情况之一：

如果左侧利润和右侧利润都小于等于预期价利润，此时满足题目要求，输出补贴或收税值。如果左侧利润和右侧利润都大于等于预期价利润，加税使右侧利润相对更大，补贴使左侧利润相对更大，无论如何 *** 作都不可能让预期价下利润最大，输出NO SOLUTION。如果左侧利润高于预期价利润，且预期价利润大于等于右侧利润，为了让预期价利润为最大值，那么应该相对预期价利润减少左侧利润，应该收税。此时问题为应该收多少税，通过二分查找找到应该收税的最小值。
收税值范围为 1 ∼ 1 0 5 1sim10^5 1∼105，如果右侧利润高于预期价利润，或左右侧利润都小于等于预期价利润，此时取二分左侧部分（减少征税），如果不满足，取二分右侧部分（增加征税）。记录可以使左右侧利润都小于等于预期价利润的最小收税值。如果右侧利润高于预期价利润，且预期价利润高于左侧利润，为了让预期价利润为最大值，那么应该相对预期价利润减少右侧利润，应该补贴。此时问题为应该补贴多少，通过二分查找得到应该补贴的最小值。
补贴值范围为 1 ∼ 1 0 5 1sim10^5 1∼105，如果左侧利润高于预期价利润，或左右侧利润都小于等于预期价利润，此时取二分左侧部分（减少补贴），如果不满足，取二分右侧部分（增加补贴）。记录可以使左右侧利润都小于等于预期价利润的最小补贴值。

【注】本题数据比较水，不用二分，用枚举也能过。本文后面给出了几组测试数据，测试了一些极端情况，必须使用二分才能过。

【题解代码】 解法1：二分

#include
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";
        else
            cout << -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";
        else
            cout << 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 ) O(n^2) O(n2)复杂度的算法都过不了。测试变量范围：一些量不设成long long过不了。将预期价设为价格列表最后一项时的情况。

100000
1 100000
100000 1
-1 -1
1

输出：-99997