贤鱼的刷题日常--P1023 [NOIP2000 普及组] 税收与补贴问题--题目详解

简介: 🍀学习了解P1023 [NOIP2000 普及组] 税收与补贴问题
🏆今日学习目标:
🍀学习了解P1023 [NOIP2000 普及组] 税收与补贴问题
✅创作者:贤鱼
⏰预计时间:15分钟

请添加图片描述

题目

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

题目背景

每样商品的价格越低,其销量就会相应增大。现已知某种商品的成本及其在若干价位上的销量(产品不会低于成本销售),并假设相邻价位间销量的变化是线性的且在价格高于给定的最高价位后,销量以某固定数值递减。(我们假设价格及销售量都是整数)

对于某些特殊商品,不可能完全由市场去调节其价格。这时候就需要政府以税收或补贴的方式来控制。(所谓税收或补贴就是对于每个产品收取或给予生产厂家固定金额的货币)

题目描述

你是某家咨询公司的项目经理,现在你已经知道政府对某种商品的预期价格,以及在各种价位上的销售情况。要求你确定政府对此商品是应收税还是补贴的最少金额(也为整数),才能使商家在这样一种政府预期的价格上,获取相对其他价位上的最大总利润。

总利润=单位商品利润 $ \times $ 销量

单位商品利润=单位商品价格 - 单位商品成本 (- 税金 or + 补贴)

输入格式

输入的第一行为政府对某种商品的预期价,第二行有两个整数,第一个整数为商品成本,第二个整数为以成本价销售时的销售量,以下若干行每行都有两个整数,第一个为某价位时的单价,第二个为此时的销量,以一行 -1 -1 表示所有已知价位及对应的销量输入完毕,输入的最后一行为一个单独的整数表示在已知的最高单价外每升高一块钱将减少的销量。

输出格式

输出有两种情况:若在政府预期价上能得到最大总利润,则输出一个单独的整数,数的正负表示是补贴还是收税,数的大小表示补贴或收税的金额最小值。若有多解,取绝对值最小的输出。

如在政府预期价上不能得到最大总利润,则输出 NO SOLUTION

样例 #1

样例输入 #1

31
28 130
30 120
31 110
-1  -1
15

样例输出 #1

4

提示

所有数字均小于 $10^5$

思路

这个题主要解决的有一下三个方面

不改价格的情况下找找符合题目要求的数据
补贴下找到符合题目要求的数据
税收下找到符合题目要求的数据

所以这个题的思路非常明确

由于是线性数据,第一个一定是最小,最后一个一定是最大

我们要算出数据的斜率来算出每个销售量下的售价才能找到题目要求的数据
如果用k记录斜率
xjg是上一个的价格,jg是现在的价格,xs是现在的售价,xxs是上一个的售价

那么斜率k[xjg]=(xs-xxs)/(jg-xjg);

斜率出来了后面的算出每一个销售量下的售价也就好算了
用num[i]储存i销售量下的价格
那么如果num此时为空
这里的xk就为斜率,xxjg等于当前价格,nm等于i销售量下的售价

num[i]=xk*(i-xxjg)+nm;

到此为止,我们需要的数据都算完了,接下来按照题目要求寻找答案就可以了

AC代码

#include<cmath>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int mb,ans,jg,xs;
double k[1010101],num[1010101];
int main(){
    cin>>mb;
    cin>>jg>>xs;
    int minj=jg;
    int xjg,xxs;//这里先储存一下最小的价格和销售量
    while(jg!=-1&&xs!=-1){
        xjg=jg,xxs=xs;
        num[jg]=xs;//由于最后一位输入-1,所以这里就可以储存最大的售价和对应销售量
        cin>>jg>>xs;
        k[xjg]=(xs-xxs)/(jg-xjg);//这里计算斜率
    }
    int yd;
    cin>>yd;
    int xk;
    int xxjg;
    int nm;
    for(int i=minj;i<=xjg;i++){
        if(!num[i]){
            num[i]=xk*(i-xxjg)+nm;
        }else{
            xk=k[i];
            xxjg=i;
            nm=num[i];
        }
    }
    int max=-1;
    while(xxs-yd>0) xjg++,xxs-=yd,num[xjg]=xxs;//处理一下比最大售价还大的售价对应的销售量
    for(int i=minj;i<=xjg;i++){//首先先看看没有修改价格的最大利润
        if((i-minj)*num[i]>max) ans=i,max=(i-minj)*num[i];
    }
    if(ans==mb){//符合题意直接输出
        cout<<0;
        return 0;
    }
    if(ans>mb){//如果不改价格的数据和要求不同,按照要求处理
        for(int i=1;i>=0;i++){//这一层代表修改的价格
            ans=0,max=-1;
            for(int j=minj;j<=xjg;j++)//从最小价格到最大价格
            if((j-minj+i)*num[j]>=max){//这里按照题目要求处理就可以了
                ans=j;
                max=(j-minj+i)*num[j];
            }
            if(ans==mb){
                cout<<i;
                return 0;
            }
        }
    }else{
    for(int i=-1;i<=0;i--){//这里让i--,实现了降低价格的作用![请添加图片描述](https://ucc.alicdn.com/images/user-upload-01/8b448e31e8934743ba23d3593036cb57.gif)

            ans=0,max=-1;
            for(int j=minj+1;j<=xjg;j++)//和上面同理
            if((j-minj+i)*num[j]>=max){
                ans=j;
                max=(j-minj+i)*num[j];
            }
            if(ans==mb){
                cout<<i;
                return 0;
            }
        }

    }
    cout<<"NO SOLUTION";
    return 0;
}

请添加图片描述

相关文章
|
关系型数据库 MySQL 数据库
实时计算 Flink版产品使用合集之支持将数据写入 OceanBase 数据库吗
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
261 5
Vue2竖向文字滚动
这是一个基于Vue3的文字滚动组件(TextScroll),支持自定义滚动文字数组、滚动间隔时间、展示宽度及高度等属性。该组件通过VerticalTextSlider.vue实现,提供了平滑过渡动画,并允许鼠标悬停时暂停滚动。适用于多种场景下的文字轮播需求。
269 0
Vue2竖向文字滚动
|
12月前
|
存储 安全 大数据
CDGA|数据流通新策略:高效利用,解锁数字经济新动能
在数字化时代,数据成为推动经济社会发展的关键要素。然而,数据孤岛、安全隐私及标准化不足等问题制约了其高效利用。本文探讨数据流通的新策略,包括强化数据治理、技术创新、安全保护及标准化建设,旨在构建高效利用体系,赋能数字经济高质量发展,激发数据要素潜能,推动产业升级与经济转型。
|
12月前
|
自然语言处理 NoSQL 前端开发
基于Neo4j的水稻病虫害问答系统
基于Neo4j的水稻病虫害问答系统
160 1
|
Kubernetes Cloud Native Linux
云原生入门:Kubernetes的简易部署与应用
【8月更文挑战第49天】在云原生的世界里,Kubernetes(K8s)是一颗璀璨的星。本文将带你走进K8s的世界,从安装到简单应用,轻松驾驭这个强大的容器编排工具。让我们一起探索云原生的奥秘,解锁新技能!
|
存储 负载均衡 监控
Linux-虚拟机迁移步骤
虚拟机迁移步骤
496 0
|
分布式计算 DataWorks NoSQL
DataWorks产品使用合集之怎么离线同步MongoDB的增量数据
DataWorks作为一站式的数据开发与治理平台,提供了从数据采集、清洗、开发、调度、服务化、质量监控到安全管理的全套解决方案,帮助企业构建高效、规范、安全的大数据处理体系。以下是对DataWorks产品使用合集的概述,涵盖数据处理的各个环节。
|
开发框架 算法 Linux
【知识点回顾 】Qt信号槽与Linux信号处理 的处理机制 深入探讨
【知识点回顾 】Qt信号槽与Linux信号处理 的处理机制 深入探讨
311 0
|
网络协议 安全 网络安全
软考中级之数据库系统工程师笔记总结(五)网络基础
软考中级之数据库系统工程师笔记总结(五)网络基础
161 0
|
机器学习/深度学习 传感器 算法
WOA-BP回归预测 | Matlab 鲸鱼优化算法优化BP神经网络回归预测
WOA-BP回归预测 | Matlab 鲸鱼优化算法优化BP神经网络回归预测