这道题的原型是餐巾计划问题,来源线性规划和网络流24题.
 但是这题n<=100000,跑费用流显然是过不了的.
 证明网上只有vfk的,然而并看不懂.大概的意思是费用流建图后,每次跑最短路,最短路的长度都是递减的,而流量就是玩具的个数,意即单位玩具的费用是随购买玩具的个数递减的.也就是说f(x)是一个单峰函数.
 这里有一个容易想到但是会WA的贪心,然而我看不懂那些题解里面关于卡这个贪心的样例到底是什么鬼...
 这个贪心的思想是每次从左往右扫,先只用玩具但不消毒,留着用.如果碰到玩具不够的情况,就找最早用完留着没处理的玩具,把它们能送慢洗店就送慢洗店,否则送快洗店,以满足当天的玩具需求.
 这个数据可以卡掉这个做法:D=4,N1=1,N2=3,C1=3,C2=1,Tc=4,T1=3,T2=1,T3=1,T4=4.
 最优方案是买4个玩具,第二天送一个去快洗店,第一天送3个去慢洗店,费用为25.
 错误的贪心则会产生26的费用,因为它会在第三天的时候发现玩具不够用,然后在第一天送一个去快洗店,这样一来第一天就只有两个未处理的玩具.把这两个玩具送去慢洗,还必须把第二天和第三天的玩具送去快洗,这样第四天才有足够的玩具,这样产生的费用就会变多.
 正确的贪心也是好想的,慢洗店的方法不变,快洗店则在慢洗无法满足要求的时候,优先选择消毒那些最晚用完留着没处理,且能够在当天之前洗完的玩具.
 一般做法两个队列就好了,我比较傻还要开个并查集维护一下...
 using namespace std;
 int ans;
 int fa[maxn];
 return res;
 ans=inf;
 printf("%d\n",ans);