J.Printout

题目：链接：

题目：

小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
     
      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
      
       >money[i].page;        if(money[i].page>n&&res1!=1)        {            res=i;res1=1;        }    }   // cout<<"res="<
       
        <
        
         >money[i].doll;    int book=0;    cun[0]=n*money[res].doll;    for(int i=res;i