题意:

有n个订单和可以在m小时内制作月饼,制作月饼不考虑时间(即,你可以在一个时刻在所有需要的月饼都做完)

接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼

接下来一行t,s表示制作的月饼可以保质t小时,每保质一小时需要花费s的价值

接下来m行表示从第0小时开始在该时间制作月饼的花费的价值(2000年1月1日0时表示第0个小时)

求完成所有订单消耗的最小价值

题解:

因为题目中给的时间是年月日的,所以我们首先要把它转化为距离2000年1月1日0时多少小时

然后又因为我们需要求最小花费,对于一个订单,你可以在该订单结束的时刻(设为距离2000年1月1日0时x小时)的区间[0,x]内中选择花费最少的一天去制作月饼。

这就可以用到单调队列,构造一个从左向右递增的序列即可。这样的话对于x时刻的月饼,我们只需要找到单调队列中那个最左边满足题意得就可以了

如果这样的话,那么这个单调队列按照从左向右递增的这个值就要考虑到保质花费,和在那个时刻做月饼得花费。具体见代码吧

代码:

 1 #include <stdio.h>
2 #include <string.h>
3 #include <stdlib.h>
4 #include <iostream>
5 #include <algorithm>
6 #include<map>
7 using namespace std;
8 typedef long long LL;
9 typedef unsigned long long ull;
10 const int inf=0x3f3f3f3f;
11 const LL INF=0x3f3f3f3f3f3f3f3fll;
12 const int maxn=1e5+5;
13 map<string,int>mp;
14 int n,m,time[3050],sum[15],S,T,cost[100050],q[100050];
15 LL num[3000];
16 void init()
17 {
18 mp["Jan"]=1,mp["Feb"]=2,mp["Mar"]=3,mp["Apr"]=4,mp["May"]=5,mp["Jun"]=6,mp["Jul"]=7,mp["Aug"]=8;
19 mp["Sep"]=9,mp["Oct"]=10,mp["Nov"]=11,mp["Dec"]=12;
20 sum[0]=0,sum[1]=31,sum[2]=sum[1]+28,sum[3]=sum[2]+31,sum[4]=sum[3]+30,sum[5]=sum[4]+31,sum[6]=sum[5]+30;
21 sum[7]=sum[6]+31,sum[8]=sum[7]+31,sum[9]=sum[8]+30,sum[10]=sum[9]+31,sum[11]=sum[10]+30;
22 }
23
24 int get(int y,int m,int d,int t) //获取这个时间对应的2000年1月1日0点有多少小时
25 {
26 int ans=0;
27 for(int i=2000; i<y; i++)
28 {
29 if((i%4==0&&i%100!=0)||i%400==0)
30 ans+=366;
31 else
32 ans+=365;
33 }
34 if((y%4==0&&y%100!=0)||y%400==0)
35 {
36 ans+=sum[m-1];
37 if(m-1>=2)ans++;
38 }
39 else
40 {
41 ans+=sum[m-1];
42 }
43 ans+=(d-1);
44 return ans*24+t;
45 }
46
47 int main()
48 {
49 init();
50 while(~scanf("%d%d",&n,&m))
51 {
52 if(n==0&&m==0)break;
53 for(int i=0; i<n; i++)
54 {
55 int year,day,t;
56 char mon[10];
57 scanf("%s%d%d%d%I64d",mon,&day,&year,&t,&num[i]);
58 time[i]=get(year,mp[mon],day,t);
59 //printf("->%d\n",time[i]);
60 }
61 scanf("%d%d",&T,&S);
62 int tail=0,head=0,k=0;
63 LL cnt=0;
64 for(int i=0; i<m; i++)
65 {
66 scanf("%d",&cost[i]);
67 /*
68 维护一个递增的序列,这个递增的值是花费多少才能使月饼保存到第i个小时
69 */
70 while(head<tail&&cost[q[tail-1]]+S*(i-q[tail-1])>=cost[i])tail--;
71 q[tail++]=i;
72 while(i==time[k]) //当这个条件触发时,就可以从单调队列中拿出来你从0时刻到现在那个最小的花费
73 { //但是还要判断一下保鲜时间超时了没有
74 while(head+1<tail&&(i-q[head]>T))head++;
75 cnt+=num[k]*(cost[q[head]]+S*(i-q[head]));
76 k++;
77 }
78 }
79 printf("%I64d\n",cnt);
80 }
81 return 0;
82 }

最新文章

  1. 报错: Unable to start activity ComponentInfo:You need to use a Theme.AppCompat theme
  2. jquery扩展(- _ -//
  3. java父类与接口有相同的方法
  4. MxNet Windows下安装
  5. Greedy:Yogurt factory(POJ 2393)
  6. 搭建和使用Docker私有仓库
  7. Node.js之【express 安装问题】
  8. 查看linux版本的三种常用方法
  9. QT学习 之 QwtPlot(数学绘图)
  10. STL之sort函数的用法
  11. ONES 安装、配置以及初始化配置
  12. metasploit魔鬼训练营 (安全漏洞生命周期)
  13. 委托初级篇——lambda表达式的推导
  14. Splunk 简单笔记
  15. sql 日志文件截断收缩
  16. HDU 5984 数学期望
  17. 基于SSH的高校网上选课系统的质量属性的实现
  18. Oracle的SQL语句中如何处理‘&amp;’符号
  19. 04. pt-deadlock-logger
  20. Linux 系统下 centOS 7 ipconfig 提示没有安装

热门文章

  1. 基于Python的接口自动化-读写excel文件
  2. Writing in the science: Introducion
  3. 设置.ignore后不生效解决方案
  4. Session、Cookie与Token
  5. 计算起始车站车费问题-JavaScript数组对象写法
  6. std::thread线程库详解(3)
  7. Redis 实战 —— 06. 持久化选项
  8. Jmeter接口自动化测试系列之函数使用及扩展
  9. What is :: (double colon) in Python when subscripting sequences?
  10. from unittest import TestCase