标题很长emmm……
[USACO2008 NOV]toy 玩具
https://www.luogu.org/problemnew/show/P2917
https://www.lydsy.com/JudgeOnline/problem.php?id=1229
[BJWC2018]餐巾计划问题
https://www.luogu.org/problemnew/show/P4480
其中[BJWC2018]餐巾计划问题的数据范围更大，且数据强度可能更强，因此下文围绕该问题展开。
一个餐厅在相继的n天里，每天需用的餐巾数不尽相同。假设第i天(i=1,2,...,n)(i=1,2,...,n)需要ri块餐巾。餐厅可以在任意时刻购买新的餐巾，每块餐巾的费用为p。
使用过的旧餐巾，则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A，需要等待m1天后才能拿到新餐巾，其费用为c1；把一块旧餐巾送到清洗店B，需要等待m2天后才能拿到新餐巾，其费用为c2。
例如，将一块第k天使用过的餐巾送到清洗店A清洗，则可以在第k+m1天使用。
请为餐厅合理地安排好n天中餐巾使用计划，使总的花费最小。
对于50%的数据，我们有一个很经典的网络流做法洛谷1251：[网络流24题]餐巾计划问题。
但是数据规模扩大后就显然不能用网络流求解了。
分两种情况：
1.快洗店更贵：
考虑到先买和后买餐巾所对答案和过程不会造成影响，且当买餐巾c条达到最优解时，显然c+k的花费比c+k+1的花费更少。
并且不难感性证出c-k的花费比c-k-1的花费更少（会在最优情况下多次使用快洗店的餐巾使得钱变多）。
因此这是一个单峰函数，我们可以三分求解。
最便宜的显然是先使用新的毛巾，等到没了的时候使用慢洗店的，最差使用快洗店的得出答案，使用队列维护一下即可（虽然这么说，也是挺恶心的，我对着别人的代码调了3h才过，可能现在让我解释代码都解释不明白。）
2.快洗点更便宜：
那就都快洗，这是显然的。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=;
const int INF=;
inline int read(){
int X=,w=;char ch=;
while(ch<''||ch>''){if(ch=='-')w=-;ch=getchar();}
while(ch>=''&&ch<='')X=(X<<)+(X<<)+ch-'',ch=getchar();
return X*w;
}
int t[N],num[N],q[N],cnt,d,n1,n2,c1,c2,tc;
int sn,sm,so,en,em,eo;
inline void add(int x,int p){
q[en]=x;num[en++]=p;
}
int f(int k){
sn=sm=so=en=em=eo=;
int ans=(tc-c2)*k;
add(-,k);
for(int i=;i<=d;i++){
int j=t[i];
while(sn!=en&&i-q[sn]>=n1){
num[em]=num[sn];
q[em++]=q[sn++];
}
while(sm!=em&&i-q[sm]>=n2){
num[eo]=num[sm];
q[eo++]=q[sm++];
}
while(j>){
if(so!=eo){
if(num[eo-]>j){
ans+=c2*j;
num[eo-]-=j;
break;
}
else{
ans+=c2*num[eo-];
j-=num[eo-];
eo--;
}
}
else if(sm!=em){
if(num[em-]>j){
ans+=c1*j;
num[em-]-=j;
break;
}
else{
ans+=c1*num[em-];
j-=num[em-];
em--;
}
}
else return INF;
}
add(i,t[i]);
}
return ans;
}
int sfen(int l,int r){
while(){
if(r-l<=){
int m=INF;
for(int i=l;i<r;i++)m=min(m,f(i));
return m;
}
int mid1=l+(r-l)/,mid2=l+*(r-l)/;
int a=f(mid1);
if(a!=INF&&a<=f(mid2))r=mid2;
else l=mid1;
}
}
int main(){
d=read(),n1=read(),n2=read(),c1=read(),c2=read(),tc=read();
if(n1>n2){swap(n1,n2);swap(c1,c2);}
if(c1<=c2)n2=,c2=;
int tsum=;
for(int i=;i<=d;i++){
t[i]=read();tsum+=t[i];
}
printf("%d\n",sfen(,tsum+));
return ;
}
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++