BZOJ-5164: 餐厅计划问题

Description

一个餐厅在相继的n天里，每天需用的餐巾数不尽相同。假设第i天(i=1,2,...,n)需要ri块餐巾。餐厅可以在任意时刻购买新的餐巾，每块餐巾的费用为P。使用过的旧餐巾，则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A，需要等待m1天后才能拿到新餐巾，其费用为c1；把一块旧餐巾送到清洗店B，需要等待m2天后才能拿到新餐巾，其费用为c2。例如，将一块第k天使用过的餐巾送到清洗店A清洗，则可以在第k+m1天使用。请为餐厅合理地安排好n天中餐巾使用计划，使总的花费最小。1≤n≤200000，1≤m1,m2≤n，1≤c1,c2,p≤100，1≤ri≤100

三分买毛巾的个数，之后贪心，设m1< m2 c1> c2，那么先尽量用m2天前的，如果用没了，就尽量用m1天前，尽量时间靠后的毛巾，如果无法完成任务，返回的代价为inf。
代码实现上，用并查集维护每个位置前第一个有毛巾没用的天是哪天即可。
复杂度O(nlogn并查集)

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 201000 
typedef long long ll;
const ll inf=0x3f3f3f3f3f3f3f3fll;
ll c1,c2,p;
int m1,m2,n,fa[N],a[N];
int find(int x){return x==fa[x]?x:(fa[x]=find(fa[x]));}
ll cal(int x)
{
    static ll b[N];
    ll re=p*x,i,lea,sum=0,j;
    for(i=0;i<=n;++i) b[i]=a[i],fa[i]=i;
    for(i=1;i<=n;++i)
    {
        lea=b[i];
        if(x>=lea) x-=lea,lea=0;
        else lea-=x,x=0;
        if(i-m1>=1) sum+=b[i-m1],b[i-m1]=0,fa[i-m1]=0;
        if(sum>=lea) re+=c1*lea,sum-=lea,lea=0;
        else re+=c1*sum,lea-=sum,sum=0;
        if(i-m2>=1)
        {
            for(j=find(i-m2);lea&&j;j=find(j-1))
            {
                if(b[j]>=lea) re+=c2*lea,b[j]-=lea,lea=0;
                else re+=c2*b[j],lea-=b[j],b[j]=0,fa[j]=find(j-1);
            }
        }
        if(lea) return inf;
    }
    return re;
}
int main()
{
    scanf("%d%d%d%lld%lld%lld",&n,&m1,&m2,&c1,&c2,&p);
    if(c1>c2) swap(m1,m2),swap(c1,c2);
    int i;
    for(i=1;i<=n;++i) scanf("%d",a+i);
    ll l=1,r=ll(n)*10000+1,len,mid1,mid2,ans=r;
    while(r-l>6)
    {
        len=(r-l)/3; mid1=l+len; mid2=r-len;
        if(cal(mid1)<cal(mid2)) r=mid2;
        else l=mid1;
    }
    for(i=l;i<=r;++i) ans=min(ans,cal(i));
    printf("%lld",ans);
    return 0;
}