题意：月饼商店从2000年1月1日0时开始开m个小时，只能在整点的时候才能做月饼，给出每个时间点做一个月饼的费用，做月饼的时间不计，有n个订单，取货的日期和数量，商店有冷藏库，容量无限大，月饼的冷藏时间有限，冷藏是要花钱的，求出这n个订单总共最少得花多少钱。
思路：对于每个订单ti都是在ti-t—ti时间段内找出做月饼花费最小时间点，可以先求出任意时间点做月饼满足最后一个订单的费用(不考虑冷藏时限)，然后用线段树处理区间最小值，然后对于每个订单找出ti-t—ti区间的最小值，然后要减去该订单的时间到最后订单时间的冷藏费用。ti-t可能小于0，ti可能大于m。
#include<stdio.h>
#include<string.h>
const int N=100100;
int time[N],n,aa[N];
char ss[15][10]= {"Jan","Feb","Mar","Apr","May","Jun","Jul","Aug","Sep","Oct","Nov","Dec"};
int days[15]= {31,28,31,30,31,30,31,31,30,31,30,31};
struct date
{
int year,month,day,hour,cont;
}mark[N];
int min(int a,int b)
{
if(a>b)return b;
return a;
}
int leap(int year)
{
return (year%4==0&&year%100!=0)||year%400==0;
}
int tianshu(date a)//求天数
{
int ret=a.year*365+(a.year-1)/4-(a.year-1)/100+(a.year-1)/400,i;
days[1]+=leap(a.year);
for(i=0; i<a.month-1; ret+=days[i++]);
days[1]=28;
return ret+a.day;
}
int hanshu(date a,date b)//求小时
{
int rest=tianshu(a)-tianshu(b);
rest*=24;
if(b.hour<a.hour)
rest+=(a.hour-b.hour);
else rest-=(b.hour-a.hour);
return rest+b.hour;
}
void Time()
{
int i,j;
char str[10];
for(i=1; i<=n; i++)
{
scanf("%s%d%d%d%d",str,&mark[i].day,&mark[i].year,&mark[i].hour,&mark[i].cont);
for(j=0;j<12; j++)
{
if(strcmp(str,ss[j])==0)
{
mark[i].month=j+1;
break;
}
}
}
mark[0].year=2000; mark[0].month=1; mark[0].day=1;mark[0].hour=0;
for(i=1; i<=n; i++)
time[i]=hanshu(mark[i],mark[0]);//订单的时间
}
struct Tree
{
int L,R,mw;
}T[N*5];
void buildTree(int L,int R,int id)
{
T[id].L=L;T[id].R=R;
if(L==R)
{
T[id].mw=aa[L];
return ;
}
int mid=(L+R)>>1,li=id<<1,ri=li|1;
buildTree(L,mid,li);
buildTree(mid+1,R,ri);
T[id].mw=min(T[li].mw,T[ri].mw);
}
int find(int L,int R,int id)
{
if(T[id].L==L&&T[id].R==R)
return T[id].mw;
int mid=(T[id].L+T[id].R)>>1,li=id<<1,ri=li|1;
if(R<=mid)
return find(L,R,li);
else if(L>mid)
return find(L,R,ri);
else
return min(find(L,mid,li),find(mid+1,R,ri));
}
int main()
{
int m,i,tt,s;
__int64 temp,ans;
while (scanf("%d%d",&n,&m)!=EOF)
{
if (n==0 && m==0) break;
memset(time,0,sizeof(time));
Time();
scanf("%d%d",&tt,&s);
for(i=0;i<m;i++)
{
scanf("%d",&aa[i]);
if(i<=time[n])
aa[i]+=((time[n]-i)*s);
}
buildTree(0,time[n],1);
ans=0;
for(i=1;i<=n;i++)
{
if(time[i]-tt<0)
temp=find(0,min(m-1,time[i]),1);
else
temp=find(time[i]-tt,min(m-1,time[i]),1);
temp-=((time[n]-time[i])*s);
ans+=(temp*mark[i].cont);
}
printf("%I64d\n",ans);
}
return 0;
}