洛谷 P1023 税收与补贴问题 (2000NOIP提高组)
题意分析
一开始没理解题意。啰啰嗦嗦一大堆。看了别人的题解才明白啥意思。
对于样例来说,简而言之:
首先可以根据题目推算出来
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) * 110 >= (28 - 28 + x) * 130
(31-28 + x) * 110 >= (29 - 28 + x) * 125
(31-28 + x) * 110 >= (30 - 28 + x) * 120
(31-28 + x) * 110 >= (31 - 28 + x) * 110
(31-28 + x) * 110 >= (32 - 28 + x) * 95
……
(31-28 + x) * 110 >= (38 - 28 + x) * 5
说白了,就是让商家在*制定的价格时盈利最多,那么商家肯定愿意在那个价格卖。那么问题就是如何求出这个x。
其实如果算出来每个价格对应的销量之后,那么我们只需要求解下面的方程,一定可以解除min<=x<=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;
}