题解 | 税收与补贴问题-NOIP2000普及组复赛B题

B-税收与补贴问题_NOIP2000普及组复赛

https://ac.nowcoder.com/acm/contest/228/B

题目描述

每样商品的价格越低，其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量（产品不会低于成本销售），并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后，销量以某固定数值递减。（我们假设价格及销售量都是整数）
对于某些特殊商品，不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。（所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币）

你是某家咨询公司的项目经理，现在你已经知道政府对某种商品的预期价格，以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额（也为整数），才能使商家在这样一种政府预期的价格上，获取相对其他价位上的最大总利润。

总利润 = 单位商品利润 * 销量
单位商品利润 = 单位商品价格 – 单位商品成本（– 税金 or + 补贴）

输入描述:

输入的第一行为政府对某种商品的预期价，第二行有两个整数，第一个整数为商品成本，第二个整数为以成本价销售时的销量售，以下若干行每行都有两个整数，第一个为某价位时的单价，第二个为此时的销量，以一行-1，-1表示所有已知价位及对应的销量输入完毕，输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输出描述:

输出有两种情况：若在政府预期价上能得到最大总利润，则输出一个单独的整数，数的正负表示是补贴还是收税，数的大小表示补贴或收税的金额最小值。若有多解，取绝对值最小的输出。
如在政府预期价上不能得到最大总利润，则输出“NO SOLUTION”.

示例1

输入

31
28 130
30 120
31 110
-1 -1
15

输出

4

解答

题意分析
一开始没理解题意。啰啰嗦嗦一大堆。看了别人的题解才明白啥意思。
对于样例来说，简而言之：
首先可以根据题目推算出来
28 130
29 125
30 120
31 110
32 95
33 80
34 65
35 50
36 35
37 20
38 5
表示在某个金额时的销量。在金钱为39的时候，销量为负数，肯定是不能盈利的。
我们假设题目所求的补贴/收税金额为x(正数表示补贴，负数表示收税)，那么题目要求我们算出绝对值最小的x，使得下列不等式均成立。
$(31-28 + x) \times 110 \geq (28 - 28 + x) \times130$
$(31-28 + x)\times110 \geq (29 - 28 + x) \times 125$
$(31-28 + x) \times 110\geq (30 - 28 + x) \times120$
$(31-28 + x)\times 110 \geq (31 - 28 + x) \times 110$
$(31-28 + x) \times 110 \geq (32 - 28 + x)\times95$
……
$(31-28 + x) \times 110\geq (38 - 28 + x) \times 5$

说白了，就是让商家在政府制定的价格时盈利最多，那么商家肯定愿意在那个价格卖。那么问题就是如何求出这个x。
其实如果算出来每个价格对应的销量之后，那么我们只需要求解下面的方程，一定可以解除 $min\leq x\leq max$ 。然后就可以找到x绝对值最小的数。
并且根据政府期望商家卖的价钱分为两部分，第一部分求得最小值，第二部分求得最大值，即可。

代码总览

#include <bits/stdc++.h>
#define nmax
using namespace std;
typedef struct item{
    int Price;
    int Sales;
}item;
int GovPrice = 0;
int Cost = 0, SalesAtCost = 0,TargetSales = 0;
int TempPrice = 0, TempSales = 0;
int DecreaseMount = 0;
vector<item> v;
bool cmp(item a, item b)
{
    return a.Price<b.Price;
}
void PricePocess()
{
    int tag = v.size();
    int gapNum,gapDec;
    item head,tail;
    for(int i = 0;i<tag-1;++i){
        head = v[i];
        tail = v[i+1];
        gapNum = tail.Price - head.Price;
        if(gapNum == 1) continue;
        else{
            gapDec = (tail.Sales - head.Sales) / gapNum;
            int Temp = head.Sales;
            for(int j = 1;j<gapNum;++j){
                Temp+=gapDec;
                v.push_back({head.Price+j,Temp});
            }
        }
    }
    sort(v.begin(),v.end(),cmp);
    tag = v.size();
    TempPrice = v[tag-1].Price;
    TempSales = v[tag-1].Sales;
    while(1){
        TempPrice++;
        TempSales-=DecreaseMount;
        if(TempPrice<=0 || TempSales<=0) break;
        else{
            v.push_back({TempPrice,TempSales});
        }
    }
}
int main()
{

    //freopen("in.txt","r",stdin);
    v.clear();
    scanf("%d",&GovPrice);
    scanf("%d %d",&Cost,&SalesAtCost);
    v.push_back({Cost,SalesAtCost});
    while(scanf("%d %d",&TempPrice,&TempSales)){
        if(TempPrice == -1 && TempSales == -1) break;
        item temp = {TempPrice,TempSales};
        v.push_back(temp);
    }
    scanf("%d",&DecreaseMount);
    sort(v.begin(),v.end(),cmp);
    PricePocess();
    sort(v.begin(),v.end(),cmp);
    int PriceTag = -1;
    for(int i=0;i<v.size();++i){
        //printf("%d %d\n",v[i].Price,v[i].Sales);
        if(v[i].Price == GovPrice){
            PriceTag = i;
            TargetSales = v[i].Sales;
            break;
        }
    }
    if(PriceTag == -1){
        printf("NO SOLUTION\n");
        return 0;
    }else{
        int MoneyForOne = GovPrice - Cost;
        double LimitMax = 100000000 ,LimitMin = -1000000000;
        for(int i = 0;i<PriceTag;++i){
            double TempLimit =  1.0 * (MoneyForOne * TargetSales - ((v[i].Price-Cost)*v[i].Sales) ) /  (v[i].Sales - TargetSales);
            LimitMax = min(TempLimit,LimitMax);
        }
        for(int i = PriceTag+1;i<v.size();++i){
            double TempLimit =  1.0 * ((v[i].Price-Cost)*v[i].Sales - MoneyForOne * TargetSales )  /  (TargetSales - v[i].Sales);
            LimitMin = max(TempLimit,LimitMin);
        }
        int ans = 0;
        //printf("%f %f\n",LimitMin,LimitMax);
        if(LimitMin > LimitMax){
            printf("NO SOLUTION\n");
            return 0;
        }else if(LimitMin > 0){
            if(fabs((LimitMin) - (int)(LimitMin)) > 1e-6) ans = (int)LimitMin + 1;
            else ans = (int)LimitMin;
        }else if(LimitMax < 0){
            if(fabs((LimitMax) - (int)(LimitMax)) > 1e-6) ans = (int)LimitMax - 1;
            else ans = (int)LimitMax;
        }
        printf("%d\n",ans);
    }
    return 0;
}

来源：pengwill97