Jobs through Pipelines

题意

给定 $n$ 个任务，第 $i$ 个任务的工作量为 $a_i$，这些任务依次进入一个有 $m$ 个阶段的流水线。

在处理之前，可以将序列的前 $t$ 个任务整体移动到末尾，相当于对原数组进行一次循环移位。

然后将得到的序列划分成不超过 $k$ 个非空连续段，每一段作为一个 batch。一个 batch 的工作量就是这一段所有任务工作量之和。

问如何选择循环移位方式以及分段方式，使所有任务完成的最早时间最小。

思路

一、先考虑固定的分段方式

假设最后被分成了若干个 batch，它们的工作量分别为：

$$b_1,b_2,\cdots,b_s$$

其中：

$$\sum b_i=\sum a_i$$

设：

$$M=max⁡biM=\max b_i$$

对于流水线：

  • 第一批经过第 1 阶段需要 $b_1$；

  • 后面的 batch 按顺序进入；

  • 每个阶段之间会形成流水。

可以得到：

$$\text{最终完成时间} = \sum b_i+(m-1)\max b_i$$

而：

$$b_i=\sum a_i$$

是固定的。

所以原问题就变成：

让所有 batch 中的最大工作量尽可能小。

也就是：

$$\min \max(b_i)$$

二、转化成环上的分段问题

看到这个最小化最大值就想到了二分

然后因为我们可以把前面的若干个元素移动到末尾，所以本质上就是：

把一个环形数组分成不超过 k 段，使每段的元素和都不超过某个值 x。

于是可以二分答案。

那么问题变成：

能不能通过选择一个循环起点，把整个环分成不超过 $k$ 段，并且每段的和都 $\le x$？

记这个判断函数为：

1
check(x)

如果可以，就继续缩小答案，否则增大答案。

三、把环复制成链

为了方便处理循环，我们把数组复制一遍：

1
2
b[i]=a[i];
b[i+n]=a[i];

于是：

1
a1 a2 a3 ... an a1 a2 a3 ... an

如果从位置 $i$ 开始，只需要在这个长度为 $2n$ 的数组中考虑区间：

$[i,i+n)$

就相当于从环上的 $i$开始走一圈。

四、双指针求 nxt

对于每个位置 $i$，我们希望知道：

从 $i$ 开始，最多可以取多少个连续元素，使得这一段的总和不超过 $x$。

设：

1
nxt[i]

表示第一个没有被这一段包含的位置。

例如：

1
2
a = 2 3 1 4
x = 5

从第一个位置开始：

1
2+3=5

所以：

1
nxt[1]=3

表示：

1
[1,3)

这一段可以作为一个 batch。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
int r=1;
ll cur=0;
for(int l=1;l<=2*n;++l){
	if(r<l){
		r=l;cur=0;
	}
	while(r<=2*n && cur+b[r]<=x){
		cur+=b[r];
		r++;
	}
	nxt[l]=r;
	cur-=b[l];
}

因为 r 只会不断向右移动，所以这一部分是：

$O(n)$

第一版 直接暴力

如果直接枚举起点然后一直跳

有了 nxt 之后，最容易想到的就是：

1
2
3
4
5
6
7
8
for(int i=1;i<=n;++i){
	int p=i;
	for(int j=1;j<=k;++j){
		p=nxt[p];
		if(p>=i+n) return true;
	}
}
return false;

意思非常简单：

从 i 开始：

1
2
3
4
5
6
7
i
↓
nxt[i]
↓
nxt[nxt[i]]
↓
...

最多跳 $k$ 次。

如果能跳到：

1
p>=i+n

说明已经覆盖了完整的一圈。

这个方法思路是对的，但是复杂度是：

$O(nk)$

$n,k≤5e5$

也是成功的TLE了哈哈

第二版 倍增优化

1. 为什么想到倍增？

第一版最大的问题在于：

1
2
for(int j=1;j<=k;++j)
    p=nxt[p];

我们实际上是在做一件事情：

从 $i$ 开始，连续跳 $k$ 次 nxt。

既然是连续跳很多次，那么自然可以想到倍增

2. 定义倍增数组

定义：

1
up[i][j]

表示：

从 $i$ 出发，连续跳 $2^j$ 次之后到达的位置。

当 $j=0$ 时：

1
up[i][0]=nxt[i];

然后：

$$up[i][j] = up[up[i][j-1]][j-1]$$

代码：

1
2
3
4
5
6
7
for(int i=1;i<=n;++i)
    up[i][0]=nxt[i];
for(int j=1;j<25;++j){
    for(int i=1;i<=n;++i){
        up[i][j]=up[up[i][j-1]][j-1];
    }
}

3. 查询跳 $k$ 次

假设需要从 $i$ 开始跳 $k$ 次。

将 $k$ 进行二进制分解。

例如：

$$k=13=8+4+1$$

那么就可以：

  • 跳 $8$ 次；
  • 再跳 $4$ 次；
  • 再跳 $1$ 次。

代码：

1
2
3
4
5
int p=i;
for(int j=19;j>=0;--j){
    if(k&(1<<j))
        p=up[p][j];
}

这样原来的：

$O(k)$

就变成了：

$O(log⁡k)$

4. 第二版复杂度

预处理倍增：

$O(n\log k)$

每个起点查询：

$O(\log k)$

一共有 $n$ 个起点，所以一次 check：

$O(n\log k)$

再进行二分：

$O(n\log k\log \sum a_i)$

虽然比第一版快了很多，但是还是TLE,需要优化

第三版 把 nxt 看成函数图

1. 重新观察 nxt

对于每一个位置 $i$，nxt[i] 都唯一确定。

也就是说：

1
i -> nxt[i]

每个点都只有一条出边。

这实际上就是一张函数图。

函数图有一个非常重要的性质：

每一个连通块最终一定会进入一个环。

结构类似：

1
2
3
4
5
6
7
8
9
1
↓
2
↓
3 → 4
    ↓
    5
   ↙ ↘
  6 ← 7

也就是：

1
若干棵树 -> 一个环

2. 为什么函数图有用？

第一版是在问：

从 $i$ 开始跳 $k$ 次以后能不能覆盖一整圈？

第二版使用倍增，是为了快速跳 $k$ 次。

但是我们进一步发现：

我们其实并不关心“跳 $k$ 次以后具体在哪”。

我们真正关心的是：

连续选择若干段以后，总共覆盖了多少个元素？

而：

1
nxt[i]-i

正好就是从 $i$ 出发选择这一段时能够覆盖的长度。

因此可以把每条边：

1
i -> nxt[i]

看成一条长度为：$nxt[i]-i$ 的边。

这样问题就变成：

能不能在函数图上找到不超过 $k$ 条连续的边，使这些边覆盖的总长度至少为 $n$？

这就有机会摆脱倍增。

3.第三版中遇到的问题

1. 将 nxt 映射回 $1\sim n$

因为原数组是环，所以需要把：

1
nxt[i]

映射回原来的 $1\sim n$。

当时可以写：

1
fa[i]=(nxt[i]-1)%n+1;

这样就能建立：

1
i -> fa[i]

的函数图。

但是这里存在一个很容易忽略的问题。

2. nxt[i] >= i+n 的特殊情况

假设：

1
2
3
n=5
i=3
nxt[i]=11

那么从位置 $3$ 开始：

1
3 4 5 1 2

已经完整覆盖了一整圈。

所以实际上应该认为：

1
3 -> 3

因为从 $3$ 出发已经绕了一圈，又回到了 $3$。

但是如果直接：

1
fa[i]=(nxt[i]-1)%n+1;

那么：

$${(11-1)\bmod5+1}{} =1$$

得到：

1
3 -> 1

这显然不对。

3. 如何解决？

如果存在：

1
nxt[i]>=i+n

说明从 $i$ 出发只需要一段就已经覆盖完整个环。

那么当前 $x$ 肯定可行。

所以直接：

1
2
3
4
for(int i=1;i<=n;++i){
    if(nxt[i]>=i+n)
        return true;
}

这样不仅解决了这个特殊情况，也避免了后面的错误映射。

第四版 函数图+拓扑找环 + 环上双指针

现在我们已经知道：

1
i -> fa[i]

是一张函数图。

接下来就可以利用函数图的结构。

1
2
3
4
5
memset(ind,0,sizeof(ind));
for(int i=1;i<=n;++i){
    fa[i]=(nxt[i]-1)%n+1;
    ind[fa[i]]++;
}

其中：

1
ind[i]

表示点 $i$ 的入度。

1.利用拓扑排序找出所有环

函数图中：

不在环上的点，最终一定可以被从入度为 $0$ 的点开始不断删除。

所以我们先把所有入度为 $0$ 的点加入队列：

1
2
3
4
5
queue<int> q;
for(int i=1;i<=n;++i){
    if(ind[i]==0)
        q.push(i);
}

然后不断删除：

1
2
3
4
5
6
while(!q.empty()){
    int u=q.front();
    q.pop();
    if(--ind[fa[u]]==0)
        q.push(fa[u]);
}

删除结束后：

1
ind[i]!=0

的点，就全部位于环上。

为什么只看环？

这是整个优化最关键的地方。

假设我们从某个不在环上的点开始。

由于函数图中每个点只有一个出边，所以不断走下去以后，一定会进入某个环。

而一旦进入环，后面的路径就会一直在这个环上循环。

因此最终真正决定“能否覆盖一整圈”的结构，就是这些环。

而对于一个环，我们只需要考虑环上的连续边。

2.枚举一个环

找到环以后，把环上的点依次存入：

1
vector<int> cyc;

代码：

1
2
3
4
5
6
7
8
9
10
11
for(int u=1;u<=n;++u){
	if(!ind[u]) continue;
	vector<int> cyc;
	int v=u;
	do{
		cyc.push_back(v);
		ind[v]=0;
		v=fa[v];
	}while(u!=v);
	...
}

例如环：

1
1 -> 3 -> 5 -> 1

那么：

1
cyc = [1,3,5]

3.环上的边代表什么？

假设当前环上的点是：

1
p

那么从 $p$ 出发选择一段以后：

1
nxt[p]

就是下一段的起点。

因此这一段覆盖的长度就是：

$$nxt[p]-p$$

例如：

1
2
p = 3
nxt[p] = 8

那么这一段覆盖：

1
3 4 5 6 7

一共 $5$ 个元素。

所以边：

1
3 -> 8

可以看成权值：

$$8-3=5$$

的边。

4.环上使用双指针

现在问题变成：

在一个环上找一段连续的边，使边权之和至少为 $n$，同时边数不超过 $k$。

因为所有 $a_i$ 都是正数，所以每条边覆盖的长度也是正数。

因此可以使用双指针。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int sz=cyc.size();
int rr=0;
ll sum=0;
for(int l=0;l<sz;++l){
	while(rr<l+sz && sum<n){
		int p=cyc[rr%sz];
		sum+=nxt[p]-p;
		rr++;
	}
	if(sum>=n && rr-l<=k)
		return true;
	int p=cyc[l];
	sum-=nxt[p]-p;
}

1. sum 表示什么？

表示当前双指针 [l,rr) 中所有边覆盖的长度。

例如：

1
2
3
p1 -> p2
p2 -> p3
p3 -> p4

那么：
$$
sum = (nxt[p_1]-p_1) + (nxt[p_2]-p_2) + (nxt[p_3]-p_3)
$$

2. 为什么 sum >= n？

原数组一共有 $n$ 个元素。

如果：

$$sum\ge n$$

说明当前这些连续的段已经覆盖了至少一整圈。

所以说明可以完成整个任务。

3. 为什么 rr-l <= k？

每走一条边，就相当于选择了一段。

因此：

1
rr-l

就是当前使用的段数。

如果：

1
rr-l<=k

就说明没有超过最多 $k$ 段的限制。

所以：

1
2
if(sum>=n && rr-l<=k)
    return true;

就表示找到了一种合法的分段方案。

第四版完整 check

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
bool check(ll x){
    int r=1;
    ll cur=0;
    for(int l=1;l<=2*n;++l){
        if(r<l){
            r=l;cur=0;
        }
        while(r<=2*n && cur+b[r]<=x){
            cur+=b[r];
            r++;
        }
        nxt[l]=r;
        cur-=b[l];
    }
    for(int i=1;i<=n;++i){
        if(nxt[i]>=i+n) 
            return true;
    }
    memset(ind,0,sizeof(ind));
    for(int i=1;i<=n;++i){
        fa[i]=(nxt[i]-1)%n+1;
        ind[fa[i]]++;
    }
    queue<int> q;
    for(int i=1;i<=n;++i){
        if(ind[i]==0) q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(--ind[fa[u]]==0) q.push(fa[u]);
    }
    for(int u=1;u<=n;++u){
        if(!ind[u]) continue;
        vector<int> cyc;
        int v=u;
        do{
            cyc.push_back(v);
            ind[v]=0;
            v=fa[v];
        }while(u!=v);
        int sz=cyc.size();
        int rr=0;
        ll sum=0;
        for(int l=0;l<sz;++l){
            while(rr<l+sz && sum<n){
                int p=cyc[rr%sz];
                sum+=nxt[p]-p;
                rr++;
            }
            if(sum>=n && rr-l<=k)
                return true;
            int p=cyc[l];
            sum-=nxt[p]-p;
        }
    }
    return false;
}

5.最终ans计算

假设二分得到：

1
ans

表示最小的最大段和。

流水线总完成时间为：

$$\sum a_i+(m-1)\times ans
$$
因此：

1
cout<<sum+(ll)(m-1)*ans<<"\n";

四个版本的演变

版本 核心思路 check 复杂度 问题
第一版 双指针 + 暴力跳 $k$ 次 $O(nk)$ 直接 TLE
第二版 双指针 + 倍增 $O(n\log k)$ 仍然比较慢
第三版 函数图 约 $O(n)$ 环映射存在特殊情况，容易 WA
第四版 函数图 + 拓扑找环 + 环上双指针 $O(n)$ 最终做法

整个优化过程其实就是：

1
2
3
4
5
6
7
8
9
10
11
12
13
暴力跳 k 次
      ↓
倍增优化跳跃
      ↓
发现 nxt 本质上是一张函数图
      ↓
利用函数图的环结构
      ↓
环上把“跳多少次”转化为“覆盖多少长度”
      ↓
双指针
      ↓
O(n) check

完整正确代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=5e5+5;
int n,m,k;
ll a[maxn];
int nxt[maxn*2];
ll b[maxn*2];
int fa[maxn];
int ind[maxn];
bool check(ll x){
    int r=1;
    ll cur=0;
    for(int l=1;l<=2*n;++l){
        if(r<l){
            r=l;cur=0;
        }
        while(r<=2*n && cur+b[r]<=x){
            cur+=b[r];
            r++;
        }
        nxt[l]=r;
        cur-=b[l];
    }
    for(int i=1;i<=n;++i){
        if(nxt[i]>=i+n) 
            return true;
    }
    memset(ind,0,sizeof(ind));
    for(int i=1;i<=n;++i){
        fa[i]=(nxt[i]-1)%n+1;
        ind[fa[i]]++;
    }
    queue<int> q;
    for(int i=1;i<=n;++i){
        if(ind[i]==0) q.push(i);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(--ind[fa[u]]==0) q.push(fa[u]);
    }
    for(int u=1;u<=n;++u){
        if(!ind[u]) continue;
        vector<int> cyc;
        int v=u;
        do{
            cyc.push_back(v);
            ind[v]=0;
            v=fa[v];
        }while(u!=v);
        int sz=cyc.size();
        int rr=0;
        ll sum=0;
        for(int l=0;l<sz;++l){
            while(rr<l+sz && sum<n){
                int p=cyc[rr%sz];
                sum+=nxt[p]-p;
                rr++;
            }
            if(sum>=n && rr-l<=k)
                return true;
            int p=cyc[l];
            sum-=nxt[p]-p;
        }
    }
    return false;
}
void solve()
{
    cin>>n>>m>>k;
    ll sum=0;
    ll mx=0;
    for(int i=1;i<=n;++i){
        cin>>a[i];
        b[i]=b[i+n]=a[i];
        sum+=a[i];
        mx=max(mx,a[i]);
    }
    if(k==1){
        cout<<sum*m<<"\n";
        return ;
    }
    ll l=max(mx,sum/k),r=sum,ans;
    while(l<=r){
        ll mid=(l+r)/2;
        if(check(mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    cout<<sum+(ll)(m-1)*ans<<"\n";

}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int ___T=1;
    //cin>>___T;
    while(___T--)  solve();
    return 0;
}

复杂度分析

对于一次 check(x)：

1. 双指针求 nxt

左右指针最多各移动 $2n$ 次：

$O(n)$

2. 建立函数图

每个点处理一次：

$O(n)$

3. 拓扑删除

每个点、每条边最多处理一次：

$O(n)$

4. 枚举所有环

所有环上的点总数不超过 $n$：

$O(n)$

环上的双指针中，左右指针也只会移动 $O(n)$ 次：

$O(n)$

所以一次 check：

$O(n)$

二分答案需要：

$O(\log \sum a_i)$

次。

因此总时间复杂度：

$\boxed{O(n\log\sum a_i)}$

总结

这道题真正的难点并不是二分，而是如何快速完成 check(x)。

最开始：

$O(nk)$

直接暴力跳，无法通过。

于是想到倍增：

$O(n\log k)$

虽然减少了跳跃次数，但仍然比较慢。

继续观察 nxt：

1
i -> nxt[i]

发现每个点只有一个后继，本质上是一张函数图。

函数图最终一定进入环，于是可以：

  1. 拓扑删除树上的点；

  2. 找到所有环；

  3. 将每条边看成能够覆盖的长度；

  4. 在环上使用双指针；

  5. 判断能否用不超过 $k$ 条边覆盖至少 $n$ 个元素。

最终把一次 check 降到了：

O(n)O(n)

再配合二分答案，得到最终复杂度：

$\boxed{O(n\log\sum a_i)}$

这就是整个代码从暴力 → 倍增 → 函数图 → 函数图 + 环上双指针的完整优化过程。