长春理工大学第十四届程序设计竞赛（重现赛）J

淩亂°似流年 2022-01-07 15:35 252阅读 0赞

# J.Printout #

## 题目：链接：[https://ac.nowcoder.com/acm/contest/912/J][https_ac.nowcoder.com_acm_contest_912_J] ##

## 题目： ##

小r为了打校赛，他打算去打字社打印一份包含世界上所有算法的模板。  
  
到了打字社，小r一看价格：总打印页数X0页以下(不含X0)x0元每页，X0∼X1页(不含X1)x1元每页，X1∼X2页(不含X2)x2元每页，X2∼X3页(不含X3)x3元每页，X3∼X4页(不含X4)x4  
元每页……  
  
小r转念一想，他可以多放一些白纸在模板里面，还能花更少的钱。  
  
给出小r要打印的模板页数n以及价格列表X和x，小r想知道他打印的最少花费为多少钱？  
  
注意：小r只能打印一次，不能将一篇文章分多次打印。

## 输入描述: ##

输入包含三行，  
  
第一行输入两个数n,m,(1≤n,m≤1000)  
  
，m为价格列表的长度。  
  
第二行输入m个整数，代表X0,X1,...,Xm−1,(1≤Xi≤1000)。  
  
第二行输入m个实数，代表x0,x1,...,xm−1,(0≤xi≤1)。  
  
n,X,x含义见题目描述。题目保证X为升序且Xm−1>n。

## 输出描述: ##

输出最少花费的钱数。  
  
你的答案与标准答案误差在±0.001范围以内都算正确。  
  
示例1  
输入  
190 2  
200 500  
0.2 0.15  
  
输出  
30  
  
备注:  
  
什么？你想打印的页数大于Xm−1？不行！

## **思路** ##

**先找到符合条件的打印页数，计算不添加空白纸张的话需要打印的费用，然后计算添加空白纸张后，该页数之后的所有页数与价格交叉相乘的结果，输出最小值即可。**

#include<bits/stdc++.h>
    using namespace std;
    typedef  long long ll;
    const int maxn=2e5+10;
    struct money{
    
        int page;
        double doll;
    }money[maxn];
    int main()
    {
        int n,m;
        cin>>n>>m;
        double cun[maxn];
        int res=0,res1=0;
        for(int i=0;i<m;i++)
        {
            cin>>money[i].page;
            if(money[i].page>n&&res1!=1)
            {
                res=i;res1=1;
            }
        }
       // cout<<"res="<<res<<endl;
        for(int i=0;i<m;i++)
            cin>>money[i].doll;
        int book=0;
        cun[0]=n*money[res].doll;
        for(int i=res;i<m-1;i++)
        {
            //cout<<money[i].page<<" "<<money[i+1].doll<<"mmmm"<<endl;
            cun[++book]=money[i].page*money[i+1].doll;
        }
        sort(cun,cun+book+1);
        cout<<cun[0]<<endl;
        return 0;
    }

# #

转载于:https://www.cnblogs.com/Vampire6/p/10997496.html

[https_ac.nowcoder.com_acm_contest_912_J]: https://ac.nowcoder.com/acm/contest/912/J