题解：P1023 [NOIP2000 普及组] 税收与补贴问题

LINYUHENG2 · 2025-01-31 10:34:54 · 题解

使用模拟即可。

对于每两个价格之间，因为相邻价位间销量的变化是线性的，所以我们处理每两个价格间的斜率和每一种价格的单价。

当补贴上涨时，最大利润时的价格也会随之上涨。反之，当税收上涨时，最大利润时的价格也会随之下降，所以这是一个单调递增的函数。

我们可以这么做：先计算出当不补贴或收税时计算出最大利润时的价格，如果价格大于期望，则从小到大枚举每一个补贴，如果这时最优价格是期望就输出并退出循环。如果价格小于期望，则从大到小枚举每一个税收，如果这时最优价格是期望就输出并退出循环。

上代码！

#include<bits/stdc++.h>
using namespace std;
int ex,maxn,ans,pc,lc,ln,cnt,t=1,c,n,cc;
double k[100005],num[100005],kk,nn;
int main(){
    scanf("%d",&ex);
    scanf("%d%d",&c,&n); pc=c;
    while(c!=-1&&n!=-1){
        lc=c,ln=n,num[c]=n; 
        scanf("%d%d",&c,&n);
        k[lc]=(n-ln)/(c-lc);
    }
    scanf("%d",&cnt);
    for(int i=pc;i<=lc;++i)
        if(!num[i]) num[i]=kk*(i-cc)+nn;
        else kk=k[i],cc=i,nn=num[i];
    while(ln-cnt>0) lc++,ln-=cnt,num[lc]=ln;
    for(int i=pc;i<=lc;++i) if((i-pc)*num[i]>maxn) ans=i,maxn=(i-pc)*num[i];
    if(ans==ex) puts("0");
    else if(ans>ex){
        for(int x=1;;x++){
            maxn=ans=0;
            for(int i=pc;i<=lc;++i) if((i-pc+x)*num[i]>=maxn) ans=i,maxn=(i-pc+x)*num[i];
            if(ans==ex){printf("%d",x);return 0;}
        }
    }
    else{
        for(int x=-1;;x--){
            maxn=ans=0;
            for(int i=pc+1;i<=lc;++i) if((i-pc+x)*num[i]>=maxn) ans=i,maxn=(i-pc+x)*num[i];
            if(ans==ex){printf("%d",x);return 0;}
        }
    }
    return 0;
}