题目链接：hdu 4122 Alice's mooncake shop
题意：
有n个订单和可以在m小时内制作月饼
接下来是n个订单的信息:需要在mon月,d日,year年,h小时交付订单r个月饼
接下来一行t,s表示制作的月饼可以保质t天，每保质一天需要花费s的价值
接下来m行表示从第0小时开始在该时间制作月饼的花费的价值
求完成所有订单消耗的最小价值。
题解：
这题我还是看了很久才看懂题意，我们将读入的订单处理后，实质就是在一个时间轴上求每个订单时间点i的t区间，也就是i-t<j<=i这个区间的最小成本。
那么我们就可以维护一个单调队列来维护这个最小成本，然后O(n)解决问题。
tips:订单可能有重复，所以要预处理一下。
1 #include<bits/stdc++.h> 2 #define F(i,a,b) for(int i=a;i<=b;++i) 3 using namespace std; 4 typedef pair<int,int> P; 5 6 const int N=1e5+7; 7 int n,m,ed,T,S,cost[N]; 8 int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31}; 9 P order[2600],Q[N]; 10 map<string,int>mp; 11 12 void init() 13 { 14 mp["Jan"]=1,mp["Feb"]=2,mp["Mar"]=3,mp["Apr"]=4,mp["May"]=5; 15 mp["Jun"]=6,mp["Jul"]=7,mp["Aug"]=8,mp["Sep"]=9,mp["Oct"]=10; 16 mp["Nov"]=11,mp["Dec"]=12; 17 } 18 19 bool isrui(int x){return x%400==0||x%4==0&&x%100!=0;} 20 21 void get(int year,int mon,int day,int ck,int num) 22 { 23 int o_y=2000,o_m=1,o_d=1,o_c=0,cnt=0; 24 while(year-o_y>1) 25 { 26 if(isrui(o_y))cnt+=366; 27 else cnt+=365; 28 o_y++; 29 } 30 while(year!=o_y||mon!=o_m) 31 { 32 if(isrui(o_y)&&o_m==2)cnt+=29; 33 else cnt+=month[o_m]; 34 o_m++; 35 if(o_m>12)o_m=1,o_y++; 36 } 37 cnt+=day-1; 38 order[++ed]=P(cnt*24+ck+1,num); 39 } 40 41 int main() 42 { 43 init(); 44 while(scanf("%d%d",&n,&m),n+m) 45 { 46 char mm[10]; 47 int day,year,ck,num; 48 ed=0; 49 F(i,1,n) 50 { 51 scanf("%s%d%d%d%d",mm,&day,&year,&ck,&num); 52 get(year,mp[mm],day,ck,num); 53 } 54 int tmp=1; 55 F(i,2,ed)if(order[i].first==order[tmp].first)order[tmp].second+=order[i].second; 56 else order[++tmp]=order[i]; 57 ed=tmp; 58 scanf("%d%d",&T,&S); 59 F(i,1,m)scanf("%d",cost+i); 60 int head=1,tail=0,now=1; 61 long long ans=0; 62 F(i,1,m) 63 { 64 while(head<=tail&&1ll*(Q[tail].first+(i-Q[tail].second)*S)>cost[i])tail--; 65 Q[++tail]=P(cost[i],i); 66 while(head<=tail&&i-Q[head].second>T)head++; 67 if(now<=ed&&i==order[now].first) 68 { 69 ans+=1ll*(Q[head].first+(i-Q[head].second)*S)*order[now].second; 70 now++; 71 } 72 } 73 printf("%lld ",ans); 74 } 75 return 0; 76 }