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

使用模拟即可。

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

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

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

上代码！

CPP

#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;
}

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

文章操作

相关推荐

评论

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