题目链接：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:订单可能有重复，所以要预处理一下。
#include<bits/stdc++.h>
#define F(i,a,b) for(int i=a;i<=b;++i)
using namespace std;
typedef pair<int,int> P; const int N=1e5+;
int n,m,ed,T,S,cost[N];
int month[]={,,,,,,,,,,,,};
P order[],Q[N];
map<string,int>mp; void init()
{
mp["Jan"]=,mp["Feb"]=,mp["Mar"]=,mp["Apr"]=,mp["May"]=;
mp["Jun"]=,mp["Jul"]=,mp["Aug"]=,mp["Sep"]=,mp["Oct"]=;
mp["Nov"]=,mp["Dec"]=;
} bool isrui(int x){return x%==||x%==&&x%!=;} void get(int year,int mon,int day,int ck,int num)
{
int o_y=,o_m=,o_d=,o_c=,cnt=;
while(year-o_y>)
{
if(isrui(o_y))cnt+=;
else cnt+=;
o_y++;
}
while(year!=o_y||mon!=o_m)
{
if(isrui(o_y)&&o_m==)cnt+=;
else cnt+=month[o_m];
o_m++;
if(o_m>)o_m=,o_y++;
}
cnt+=day-;
order[++ed]=P(cnt*+ck+,num);
} int main()
{
init();
while(scanf("%d%d",&n,&m),n+m)
{
char mm[];
int day,year,ck,num;
ed=;
F(i,,n)
{
scanf("%s%d%d%d%d",mm,&day,&year,&ck,&num);
get(year,mp[mm],day,ck,num);
}
int tmp=;
F(i,,ed)if(order[i].first==order[tmp].first)order[tmp].second+=order[i].second;
else order[++tmp]=order[i];
ed=tmp;
scanf("%d%d",&T,&S);
F(i,,m)scanf("%d",cost+i);
int head=,tail=,now=;
long long ans=;
F(i,,m)
{
while(head<=tail&&1ll*(Q[tail].first+(i-Q[tail].second)*S)>cost[i])tail--;
Q[++tail]=P(cost[i],i);
while(head<=tail&&i-Q[head].second>T)head++;
if(now<=ed&&i==order[now].first)
{
ans+=1ll*(Q[head].first+(i-Q[head].second)*S)*order[now].second;
now++;
}
}
printf("%lld\n",ans);
}
return ;
}