题目描述

给定一组矢量算子，要求合理部署这些算子到矩阵计算单元和向量计算单元上，以充分利用计算资源，使得整体执行时间最短。整体执行时间定义为矩阵计算单元总执行时间和向量计算单元总执行时间的最大值。

思路(暴力)

数据范围$n<=1e4$考虑暴力,因为向量单元必须连续，所以考虑直接枚举区间,将$(i,j)$这一段区间纳入向量单元其他的纳入矩阵区间，取二者的最大值再与$ans$取$min$即可

题解：

题目要求我们合理分配一组矢量算子，使其分别在矩阵计算单元和向量计算单元上执行，并且使整体的执行时间最短。由于向量计算单元的执行效率较低（矩阵计算单元的六分之一），我们需要找到一种分配方式，使得两个单元中较大的执行时间尽可能小。

我们采用 枚举区间的方法 来解决此问题。具体思路如下：

1. 前缀和计算： 我们先求出每个算子的前缀和，这样可以方便快速计算任意区间的执行时间。

2. 枚举向量单元的区间： 我们枚举区间 $(i,j)$，表示将第 $i$ 到第 $j$ 个算子部署到向量计算单元，其他算子部署到矩阵计算单元。通过前缀和，可以很快求出这段区间的总执行时间。

3. 计算执行时间并取最小值： 对于每个区间 $(i,j)$，我们计算两部分的执行时间：

   • 向量单元的执行时间：区间 $(i,j)$ 的和乘以 6。
   • 矩阵单元的执行时间：总执行时间减去区间 $(i,j)$ 的和。

   然后我们取这两个执行时间的较大值作为当前分配方案的执行时间，并不断更新全局的最优解。

4. 提前剪枝优化： 在枚举区间时，如果某段区间的向量单元执行时间已经超过当前最优解，那么我们可以直接跳过该区间，避免无效的计算。

时间复杂度分析：

• 枚举区间的复杂度是 $O(n^2)$，其中每次计算区间和是 $O(1)$ 的操作，整体复杂度为 $O(n^2)$。虽然 $n$ 可以达到 $10^4$，但是通过合理剪枝，可以有效减少无效的计算，从而优化实际运行时间。

c++

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+10;
int n, num[N]; // 存储算子执行时间的数组
int sum[N];    // 存储前缀和
int ans;       // 最终结果，最小的执行时间

signed main() {
    cin >> n; // 输入算子数量
    // 输入每个算子在矩阵计算单元的执行时间，并计算前缀和
    for(int i=1; i<=n; i++) {
        cin >> num[i];
        sum[i] = sum[i-1] + num[i]; // 计算前缀和
    }
    
    int temp = sum[n]; // temp记录所有算子在矩阵单元的总执行时间
    ans = temp; // 初始最优解设为所有算子都在矩阵单元的执行时间
    
    // 枚举区间 (i,j)，表示将 (i,j) 这段区间分配到向量单元
    for(int i=1; i<=n; i++) {
        for(int j=i; j<=n; j++) {
            int c = sum[j] - sum[i-1]; // 计算区间 (i,j) 的执行时间
            if(c * 6 >= ans) break; // 如果当前向量单元执行时间超过已有最优解，跳出循环
            int val = max(c * 6, temp - c); // 计算向量单元和矩阵单元执行时间的最大值
            ans = min(ans, val); // 更新最优解
        }
    }
    
    cout << ans << endl; // 输出最小执行时间
}

python

N = 10**4 + 10
n = 0
num = [0] * N  # 存储算子执行时间的数组
sum = [0] * N  # 存储前缀和
ans = 0        # 最终结果，最小的执行时间

# 读取输入
n = int(input())  # 输入算子数量
num = list(map(int, input().split()))  # 输入每个算子在矩阵计算单元的执行时间
num.insert(0, 0)  # 在第一个位置插入0，使得下标从1开始

# 计算前缀和
for i in range(1, n + 1):
    sum[i] = sum[i - 1] + num[i]

temp = sum[n]  # temp记录所有算子在矩阵单元的总执行时间
ans = temp  # 初始最优解设为所有算子都在矩阵单元的执行时间

# 枚举区间 (i,j)，表示将 (i,j) 这段区间分配到向量单元
for i in range(1, n + 1):
    for j in range(i, n + 1):
        c = sum[j] - sum[i - 1]  # 计算区间 (i,j) 的执行时间
        if c * 6 >= ans:
            break  # 如果当前向量单元执行时间超过已有最优解，跳出循环
        val = max(c * 6, temp - c)  # 计算向量单元和矩阵单元执行时间的最大值
        ans = min(ans, val)  # 更新最优解

# 输出最小执行时间
print(ans)

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = 10010;
        int[] num = new int[N]; // 存储算子执行时间的数组
        int[] sum = new int[N]; // 存储前缀和
        int ans;

        // 输入算子数量
        int n = scanner.nextInt();
        
        // 输入每个算子在矩阵计算单元的执行时间，并计算前缀和
        for (int i = 1; i <= n; i++) {
            num[i] = scanner.nextInt();
            sum[i] = sum[i - 1] + num[i]; // 计算前缀和
        }

        int temp = sum[n]; // temp记录所有算子在矩阵单元的总执行时间
        ans = temp; // 初始最优解设为所有算子都在矩阵单元的执行时间

        // 枚举区间 (i,j)，表示将 (i,j) 这段区间分配到向量单元
        for (int i = 1; i <= n; i++) {
            for (int j = i; j <= n; j++) {
                int c = sum[j] - sum[i - 1]; // 计算区间 (i,j) 的执行时间
                if (c * 6 >= ans) break; // 如果当前向量单元执行时间超过已有最优解，跳出循环
                int val = Math.max(c * 6, temp - c); // 计算向量单元和矩阵单元执行时间的最大值
                ans = Math.min(ans, val); // 更新最优解
            }
        }

        // 输出最小执行时间
        System.out.println(ans);
    }
}

进一步问题分析

目标是让MAX(矩阵计算时间, 向量计算时间)尽量小。通过分析，我们可以发现，如果将向量单元部署得太大，则其计算时间可能会远远超过矩阵单元，反之如果将矩阵单元部署得太多，则可能导致无法充分利用向量单元。

思路(双指针)

问题转化与单调性

假设我们使用两个指针来表示连续子序列的左右端点：

1. 当固定左端点时，逐渐增加右端点，可以观察到：
   • 矩阵单元的执行时间会逐渐减少。
   • 向量单元的执行时间会逐渐增加。
2. 当固定一个左端点，我们可以逐步增大右端点，找到一个最优的分割点，使得两者的最大值最小。

双指针的使用

我们可以使用两个指针 left 和 right 来表示连续子序列的两端：

• 每次将右指针 right 向右扩展，更新总的执行时间。
• 当向量单元的执行时间（即子序列的和乘以6倍）开始大于或等于剩余部分的矩阵单元执行时间时，我们开始考虑收缩左指针，以找到一个更小的最大值。

算法流程

1. 初始化两个指针 left 和 right，以及两个累计和 now（当前向量单元和） 和 tot（剩余矩阵单元和）。
2. 移动右指针，逐步扩大子序列范围，并更新向量单元的执行时间。
3. 当 now * 6 >= tot 时，表示向量单元的执行时间已经超过了矩阵单元的执行时间，可以考虑移动左指针，来减少向量单元的大小。
4. 每次更新 ans 记录最小的最大执行时间。

代码

java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取算子数
        int n = scanner.nextInt();
        int[] nums = new int[n];
        
        // 读取每个算子在矩阵计算单元的执行时间
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        
        int tot = 0;
        // 计算所有算子在矩阵单元的总执行时间
        for (int num : nums) {
            tot += num;
        }
        
        int ans = tot;  // 初始答案设为矩阵单元的总执行时间
        int now = 0;    // 当前向量单元的执行时间和
        int left = 0, right = 0;  // 双指针
        
        // 双指针遍历所有可能的子序列
        while (right < n) {
            tot -= nums[right];  // 将当前算子从矩阵单元中移出，放入向量单元
            now += nums[right];  // 增加当前算子在向量单元的执行时间和
            
            // 当向量单元的执行时间大于或等于矩阵单元的执行时间时，调整左指针
            while (now * 6 >= tot) {
                ans = Math.min(ans, now * 6);  // 更新答案为当前向量单元的执行时间（乘6倍）
                // 收缩左指针，减少向量单元的执行时间
                now -= nums[left];
                tot += nums[left];
                left++;
            }
            
            // 更新答案为当前矩阵单元和的最小值
            ans = Math.min(ans, tot);
            right++;
        }
        
        // 输出结果
        System.out.println(ans);
        scanner.close();
    }
}

python

# 读取输入
n = int(input())  # 读取算子数
nums = list(map(int, input().split()))  # 读取每个算子在矩阵计算单元的执行时间

# 初始化
tot = sum(nums)  # 计算所有算子在矩阵单元的总执行时间
ans = tot  # 初始答案设为矩阵单元的总执行时间
now = 0  # 当前向量单元的执行时间和
left, right = 0, 0  # 双指针

# 双指针遍历所有可能的子序列
while right < n:
    tot -= nums[right]  # 将当前算子从矩阵单元中移出，放入向量单元
    now += nums[right]  # 增加当前算子在向量单元的执行时间和
    
    # 当向量单元的执行时间大于或等于矩阵单元的执行时间时，调整左指针
    while now * 6 >= tot:
        ans = min(ans, now * 6)  # 更新答案为当前向量单元的执行时间（乘6倍）
        # 收缩左指针，减少向量单元的执行时间
        now -= nums[left]
        tot += nums[left]
        left += 1
    
    # 更新答案为当前矩阵单元和的最小值
    ans = min(ans, tot)
    right += 1

# 输出结果
print(ans)

cpp

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    // 读取算子数
    cin >> n;
    vector<int> nums(n);
    
    // 读取每个算子在矩阵计算单元的执行时间
    int total = 0;
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
        total += nums[i];
    }
    
    int ans = total; // 初始答案设为矩阵单元的总执行时间
    int now = 0;     // 当前向量单元的执行时间和
    int left = 0, right = 0; // 双指针
    
    // 双指针遍历所有可能的子序列
    while (right < n) {
        total -= nums[right]; // 将当前算子从矩阵单元中移出，放入向量单元
        now += nums[right];   // 增加当前算子在向量单元的执行时间和
        
        // 当向量单元的执行时间大于或等于矩阵单元的执行时间时，调整左指针
        while (now * 6 >= total) {
            ans = min(ans, now * 6); // 更新答案为当前向量单元的执行时间（乘6倍）
            // 收缩左指针，减少向量单元的执行时间
            now -= nums[left];
            total += nums[left];
            left++;
        }
        
        // 更新答案为当前矩阵单元和的最小值
        ans = min(ans, total);
        right++;
    }
    
    // 输出结果
    cout << ans << endl;
    
    return 0;
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

深度学习算法由一个个计算单元组成，我们称这些计算单元为算子。

对于完成矢量运的算子我们称为矢量算子，在 $NPU$ 中矩阵计算单元和向量计算单元都可以执行矢量算子，他们是独立可并行执行的，但他们的计算效率是6:1，即假设某个失量算子在矩阵计算单元上执行的时间为 $N$ ，则在向量计算单元上执行的时间为 $6N$ 。

给定一组矢量算子，假设他们都可以部署在矩阵计算单元和向量计算单元。为了充分利用计算资源，我们可以合理部署算子的执行单元，让总体的执行时间最短，总的执行时间为 $MAX$ (矩阵计算单元总的执行时间，向量计算单元总的执行时间)。

为了简化计算模型，我们约定:

1.单个算子只能部署在矩阵计算单元或向量计算单元。

2.部署在向量计算单元的算子必须是按照给定顺序连续的。

输入描述

输入格式:

第一行输入算子数 $n$

第二行输入该组算子在矩阵计算单元的执行时间 $nums$

$1<=n<= 10^4$

$1 <=nums[i] <=10^4$

输出描述

该组算子整体的最短执行时间

样例1

输入

9
1 2 3 4 5 6 7 8 9

输出

39

说明

下标 $5$ 的算子在矩阵计算单元的执行时间为 $6$ ，将它部署在向量计算单元，

执行时间变为 $6*6=36$ ，剩下的算子部署在矩阵计算单元，执行时间为 $1+2+3+4+5+7+8+9=39$ 。

总的执行时间为 $39$ ，没有比这执行时间更短的方案了。

样例2

输入

9
3 2 17 8 3 5 4 18 15

输出

66

说明

下标 $3,4$ 的算子在矩阵计算单元的执行时间为 $8,3$ ，将它部署在向量计算单元,

执行时间变为 $8 * 6 + 3 * 6 = 66$ ，剩下的算子部署在矩阵计算单元，执行时间为 $3+2+17+5+4+18+15=64$ ，

总的执行时间为 $66$ ，没有比这执行时间更短的方案了。