[NOIP2000] 提高组 洛谷P1023 税收与补贴问题
题目背景
每样商品的价格越低,其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量(产品不会低于成本销售),并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后,销量以某固定数值递减。(我们假设价格及销售量都是整数)
对于某些特殊商品,不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。(所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币)
题目描述
你是某家咨询公司的项目经理,现在你已经知道政府对某种商品的预期价格,以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额(也为整数),才能使商家在这样一种政府预期的价格上,获取相对其他价位上的最大总利润。
总利润=单位商品利润*销量
单位商品利润=单位商品价格 - 单位商品成本 (- 税金 or + 补贴)
输入输出格式
输入格式:
输入的第一行为政府对某种商品的预期价,第二行有两个整数,第一个整数为商品成本,第二个整数为以成本价销售时的销售量,以下若干行每行都有两个整数,第一个为某价位时的单价,第二个为此时的销量,以一行-1,-1表示所有已知价位及对应的销量输入完毕,输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。
输出格式:
输出有两种情况:若在政府预期价上能得到最大总利润,则输出一个单独的整数,数的正负表示是补贴还是收税,数的大小表示补贴或收税的金额最小值。若有多解,取绝对值最小的输出。
如在政府预期价上不能得到最大总利润,则输出“NO SOLUTION”。
输入输出样例
31
28 130
30 120
31 110
-1 -1
15
4
求最少需要补贴或者收税的金额,使得所有可能的定价中,只有政府预期的定价带来的收益最高。
设一个未知数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>=(32-28+x)*95
and so on
读入数据后,先根据已知信息,利用线性关系处理出每个定价对应的销量。
解每个不等式,求x的取值范围。
输出答案。
/*by SilverN*/
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int mxn=;
int tar;
int w[mxn],a[mxn];//成本,销售量
int m,v;
int main(){
scanf("%d",&tar);
int i,j;
m=;
int nw,na,lw,la;
scanf("%d%d",&w[],&a[]);
while(){
scanf("%d%d",&nw,&na);
if(nw==- && na==-)break;
lw=w[m];la=a[m];
while(w[m]<nw){
m++;
w[m]=w[m-]+;
a[m]=a[m-]-(la-na)/(nw-lw);
}
}
scanf("%d",&v);
while(a[m]-v>){
m++;
w[m]=w[m-]+;
a[m]=a[m-]-v;
}
// for(i=1;i<=m;i++)printf("%d %d\n",w[i],a[i]);//
int pos=;
for(i=;i<=m;i++)if(w[i]==tar){pos=i;break;}
if(!pos){printf("NO SOLUTION\n");return ;}
double mx=1e8,mini=-1e8;
for(i=;i<pos;i++){
double x=( (double)((w[pos]-w[])*a[pos]-(w[i]-w[])*a[i])/(double)(a[i]-a[pos]));
mx=min(x,mx);
}
for(i=pos+;i<=m;i++){
double x=( (double)((w[i]-w[])*a[i]-(w[pos]-w[])*a[pos])/(double)(a[pos]-a[i]));
mini=max(mini,x);
}
if(mini>mx)printf("NO SOLUTION\n");
else if(mini>) printf("%.0f\n",ceil(mini));
else if(mx<) printf("%.0f\n",floor(mx));
else printf("0\n");
return ;
}
最新文章
- SQL Server 诊断查询-(5)
- android常用的一些UI调试命令am,pm
- iis7+php5.6配置404错误页面的问题
- Golang 图片上绘制文字
- Objective-C ,ios,iphone开发基础:使用GDataXML解析XML文档,(libxml/tree.h not found 错误解决方案)
- Win系统下制作U盘CLOVER引导+安装原版Mavericks10.9
- linux btp 服务器 端及客户端配置
- C#_Test
- 网络子系统48_ip协议数据帧的发送
- C#,js数据排序及其操作
- [原创]HBase学习笔记(3)- Java程序访问HBase
- Scala:数组
- mongodb遇到的问题
- FileInputStream、FileReader、FileWriter和File
- net core体系-web应用程序-4net core2.0大白话带你入门-1目录
- PHP正则提取或替换img标记属性
- CSS之metra&;title&;base&;target
- 查看JVM使用的默认的垃圾收集器
- hdu 5311(暴力)
- 进程间通信--POSIX信号量