[斜率优化DP][二分]JZOJ 3169 生产汽车

Description

如前面提到，ABC的汽车工厂有N个工人，他们在一个传送带上生产汽车，工人从左到右排列，编号依次为1到N，采用流水线模式，每个人负责自己的一部分工作。

生产一台汽车需要从1号工人开始，当1号完成他的工作后，2号就会开始工作，然后是3号，最后当N号工人完成他的工作后，整个汽车生产完毕。工人们一共需要生产M台汽车，而且必须按照从1到M的顺序去生产。

对于工人i，他完成自己的工作需要Ti的时间，而对于汽车j，组装复杂度为Fj。那么工人i花在汽车j上的时间为Ti*Fj。

当某个工人完成他的工作后，他会同时把汽车交给下一个工人，没有任何时间上的延迟，因此，要保证下一个要接受汽车的工人必须是空闲的。为了满足这个要求，ABC需要为每一台汽车选择一个好时机开始制造。

ABC想知道生产完所有汽车最少需要多少时间。

 

Input

第一行输入两个整数：工人数N(1<=N<=100,000)和汽车数M(1<=M<=100,000)。

接下来N行描述每一个工人的Ti(1<=Ti<=10,000)。

接下来M行描述每一台汽车的Fj(1<=Fj<=10,000)。

Output

输出一个数表示最少需要的时间。

 

Sample Input

输入1：

3 3

2

1

1

2

1

1



输入2：

3 3

2

3

3

2

1

2



输入3：

4 5

3

2

2

2

3

1

2

1

2

 

Sample Output

输出1：

11



输出2：

29



输出3：

55

 

Data Constraint

40%的数据满足N,M<=1000。

 

Hint

样例1： 4分钟后，工人1完成1号汽车的工作，他可以立刻开始生产第2台汽车，但如果这样的话将会不满足条件，因为7分钟后，工人2完成2号汽车的工作，此时3号工人还在生产1号汽车，3号工人并不空闲，所以2号汽车在5分钟后开始生产，3号汽车在7分钟后开始生产。3台汽车全部生产完共花费11分钟。

分析

 https://blog.csdn.net/JacaJava/article/details/78998056 不太会用博客园的数学公式，就把教我的大佬的博客贴一下8

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,q[N];
ll f[N],t[N],p[N];
int tail;

double xl(int i,int j) {
    return (double)(t[i]-t[j])/(t[i-1]-t[j-1]);
}

int main() {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) scanf("%lld",&t[i]),t[i]+=t[i-1];
    for (int i=1;i<=m;i++) scanf("%lld",&f[i]);
    q[++tail]=1;
    for (int i=1;i<=n;i++) {
        while (tail>1&&xl(i,q[tail])>xl(q[tail],q[tail-1])) tail--;
        q[++tail]=i;
    }
    for (int i=2;i<=m;i++) {
        int l=1,r=tail,mid;
        double o=(double)f[i]/f[i-1];
        while (l<r) {
            mid=l+r>>1;
            if (o<xl(q[mid+1],q[mid])) l=mid+1; else r=mid;
        }
        p[i]=p[i-1]+f[i-1]*t[q[l]]-f[i]*t[q[l]-1];
    }
    printf("%lld",p[m]+f[m]*t[n]);
}