[2000年NOIP普及组] 税收与补贴问题
- 分析：根据题意，在销量随售价改变的基础上求最小的补贴或税收，本题用了打表的方式来展现售价与销量之间的关系，其中出现了几个与普遍的规律不相同的组合，对于特例我们就要进行单独考虑，在打完表后，根据利润=（售价-进价+补贴）*销量 或者 利润=（售价-进价-税收）*销量 并开一个max来求其中的利润最大值以此获得此时的j（补贴或税收）值，如果此时的价格刚好是政府所期望的就说明找到了。
-
#include<iostream>
using namespace std;
int main()
{
int a[100001][3];//前面是指第几个 后面1指价格 2指数量
int i=1,expect,cha,temp,down,zero,max,num,price,p;
cin>>expect;
while(cin>>a[i][1]>>a[i][2]&&a[i][1]!=-1&&a[i][2]!=-1)
{
i++;
if(i>2&&a[i-1][1]-a[i-2][1]>1)//两个数量之间差值大于一（特例）
{
i--;//i退回前一位去处理特例
cha=(a[i-1][2]-a[i][2])/(a[i][1]-a[i-1][1]);//特例每平均数的差值
temp=a[i][1];//记录差值
for(int j=a[i-1][1]+1;j<=temp;j++)
{
a[i][1]=j;//每一个数是当前的价格数
a[i][2]=a[i-1][2]-cha;//i的数量是前一个的数量减去差值
i++;
}
}
}
i--;//到-1-1停的，所以来个i--抵消一下
cin>>down;
zero=a[i][2];//赋值给zero推各价位数量
while(zero>0)
{
if(zero-down<0) break;//数量成负的了
else
{
zero-=down;//每次降价都减少的数量
i++;//否则i就继续加
a[i][1]=a[i-1][1]+1;//此时价格等于前一位+1
a[i][2]=zero;//将此时数量赋值
}
}
for(int j=1;j<=10000;j++)//补助
{
max=-99999;
for(int k=1;k<=i;k++)//相当于i
{
num=(a[k][1]-a[1][1]+j)*a[k][2];//利润=（售价-进价+补贴）*数量
if(num>=max)//求最大值
{
max=num;
price=a[k][1];//现在的价格
p=1;//此时j为正
}
}
if(price==expect)
{
cout<<j*p<<endl;//若此时价格等于期望值符合题意
return 0;//找到就退出
}
max=-99999;
for(int k=1;k<=i;k++)//相当于i
{
num=(a[k][1]-a[1][1]-j)*a[k][2];//利润=（售价-进价-税收）*数量
if(num>=max)//求最大值
{
max=num;
price=a[k][1];//现在的价格
p=-1;//此时j为负
}
}
if(price==expect)
{
cout<<j*p<<endl;//若此时价格等于期望值符合题意
return 0;//找到就退出
}
}
cout<<"NO SOLUTION"<<endl;
return 0;
}