2023-10-25：用go语言，假如某公司目前推出了N个在售的金融产品(1＜=N＜=100) 对于张三，用ai表示他购买了ai

福大大架构师每日一题

发布于 2023-10-27 10:12:29

1890

发布于 2023-10-27 10:12:29

文章被收录于专栏：福大大架构师每日一题

2023-10-25：用go语言，假如某公司目前推出了N个在售的金融产品(1<=N<=100)

对于张三，用ai表示他购买了ai(0<=ai<=10^4)份额的第i个产品(1<=i<=N)

现给出K(1<=K<=N)个方案，通过这些方案，能够支持将多个不同的产品进行整合

(也可以对单个产品进行优化)形成新的产品。

新的产品形成后，若用户持有了组成新产品所需的全部的原产品份额，

则能够将用户持有的原产品份额转换为新产品的份额，各原产品份额与新产品份额比例均为1:1

我们保证对于每个产品最多存在一个方案使用旧产品整合成该产品

并且根据方案产出的新产品的产品编号均大于各旧产品的产品编号

现计划根据这些方案，帮助部分愿意升级到最新产品的用户对产品进行升级

请协助工作人员计算当前用户能够转换出的最新产品份额的最大值

输入描述

第一行包含整数N，第二行包含N个整数ai，第三行包含整数K

接下来的K行，每一行代表一个方案，每一行包含整数1和M(M>=1)

L为该方案产生的新产品的编号，M代表方案所需原产品个数

接下来的M个整数代表了该方案所需的每个原产品的个数

输出描述

根据日前的份额和给出的方案，经过若干次转换，输出当前用户能够得到产品N的份额最大值

举例

输入:

2 0 0 1 0

5 2 3 4

2 1 1

3 1 2

输出:

解释:

第一步将1份1产品转化为1份2产品

第二步将1份2产品转化为1份3产品

第三步将1份3产品和1份4产品，转成为1份5产品

然后不能得到更多的5产品了，所以返回1

实在是太困惑了，上文说的意思可谓不做人，那么我们改写一下意思，变得好理解

如下是改写后的题目描述

给定一个数组arr，长度为n，产品编号从0~n-1

arr[i]代表初始时i号产品有多少份

存在一系列的产品转化方案的数组convert，长度为k，代表k个方案

比如具体某一个方案，convert[j] = {a, b, c, d, ...}

表示当前的j号方案转化出来的产品是a，转化1份a需要：1份b、1份c、1份d...

其中a、b、c、d...一定都在0~n-1范围内

并且题目保证a > Math.max(b, c, d, ....)

而且题目保证所有方案转化出来的产品编号一定是不重复的

请返回最终能得到的第n-1号商品的最大值

1 <= n <= 100

0 <= arr[i] <= 10^4

k < n

来自招商银行。

来自左程云。

答案2023-10-25：

这次代码生成用的讯飞星火，生成完后，要略微修改下代码才能通过。另外c代码的生成，一直有问题，索性就不管了。

大体过程如下：

首先，我们需要定义一个函数ok(arr, graph, aim)来判断当前的方案是否可行。这个函数的输入参数包括：

1.arr：表示每个产品的初始份额数组；

2.graph：表示产品转化方案的邻接表；

3.aim：表示目标产品编号。

在这个函数中，我们首先初始化一些变量，然后遍历所有的产品，对于每个产品，我们检查它是否可以被转化到目标产品。如果可以，我们就更新它的转化后的数量，并继续检查下一个产品。最后，我们返回一个布尔值，表示当前的方案是否可行。

接下来，我们需要定义一个函数maxValue(arr, convert)来计算当前用户能够转换出的最新产品份额的最大值。这个函数的输入参数包括：

1.arr：表示每个产品的初始份额数组；

2.convert：表示产品转化方案的二维数组。

在这个函数中，我们首先初始化一些变量，然后使用二分查找的方法来寻找最大的转化后的产品份额。具体来说，我们将转化后的产品份额范围设置为0到所有初始产品份额之和，然后不断地将范围缩小一半，直到找到一个可行的方案或者范围已经缩小到无法再缩小为止。

最后，我们需要在主函数中调用这两个函数，并输出结果。

总的时间复杂度为O(nlogn)，其中n表示产品的数量。这是因为我们需要遍历所有的产品，并对每个产品进行二分查找。总的空间复杂度为O(n)，其中n表示产品的数量。这是因为我们需要存储每个产品的初始份额数组和转化方案的邻接表。

go完整代码如下：

package main

import (
    "fmt"
)

const MAXN = 101

var indegree [MAXN]int
var help [MAXN]int
var zeroQueue [MAXN]int
var need [MAXN]int
var n int

func maxValue(arr []int, convert [][]int) int {
    n = len(arr)
    graph := make([][]int, n)
    for i := range graph {
        graph[i] = make([]int, 0)
    }
    t := make([]int, n)
    copy(indegree[:], t)
    for _, relation := range convert {
        for i := 1; i < len(relation); i++ {
            graph[relation[0]] = append(graph[relation[0]], relation[i])
            indegree[relation[i]]++
        }
    }
    l := arr[n-1] + 1
    r := 0
    for _, num := range arr {
        r += num
    }
    m := 0
    ans := arr[n-1]
    for l <= r {
        m = (l + r) / 2
        if ok(arr, graph, m) {
            ans = m
            l = m + 1
        } else {
            r = m - 1
        }
    }
    return ans
}

func ok(arr []int, graph [][]int, aim int) bool {
    l := 0
    r := 0
    for i := 0; i < n; i++ {
        help[i] = indegree[i]
        if help[i] == 0 {
            zeroQueue[r] = i
            r++
        }
    }
    t := make([]int, n)
    copy(need[:], t)
    need[n-1] = aim
    for l < r {
        cur := zeroQueue[l]
        supplement := max(need[cur]-arr[cur], 0)
        if len(graph[cur]) == 0 && supplement > 0 {
            return false
        }
        for _, next := range graph[cur] {
            need[next] += supplement
            help[next]--
            if help[next] == 0 {
                zeroQueue[r] = next
                r++
            }
        }
        l++
    }
    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    arr1 := []int{2, 0, 0, 1, 0}
    convert1 := [][]int{{4, 2, 3}, {1, 0}, {2, 1}}
    fmt.Println(maxValue(arr1, convert1))

    arr2 := []int{100, 5, 5, 0}
    convert2 := [][]int{{1, 0}, {2, 0, 1}, {3, 0, 1, 2}}
    fmt.Println(maxValue(arr2, convert2))
}

在这里插入图片描述

rust完整代码如下：

use std::cmp::max;

const MAXN: usize = 101;
static mut indegree: [i32; MAXN] = [0; MAXN];
static mut help: [i32; MAXN] = [0; MAXN];
static mut zeroQueue: [i32; MAXN] = [0; MAXN];
static mut need: [i32; MAXN] = [0; MAXN];
static mut n: i32 = 0;

fn maxValue(arr: &[i32], convert: &Vec<Vec<i32>>) -> i32 {
    unsafe {
        n = arr.len() as i32;
        let mut graph = vec![vec![] as Vec<i32>; n as usize];
        for i in 0..n {
            indegree[i as usize] = 0;
        }
        for relation in convert.iter() {
            for i in 1..relation.len() {
                graph[relation[0] as usize].push(relation[i]);
                indegree[relation[i] as usize] += 1;
            }
        }
        let mut l = arr[(n - 1) as usize] + 1;
        let mut r = 0;
        for num in arr.iter() {
            r += *num;
        }
        let mut m = 0;
        let mut ans = arr[(n - 1) as usize];
        while l <= r {
            m = (l + r) / 2;
            if ok(&arr, &graph, m) {
                ans = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        ans
    }
}

fn ok(arr: &[i32], graph: &Vec<Vec<i32>>, aim: i32) -> bool {
    unsafe {
        let mut l = 0;
        let mut r = 0;
        for i in 0..n {
            help[i as usize] = indegree[i as usize];
            if help[i as usize] == 0 {
                zeroQueue[r as usize] = i;
                r += 1;
            }
        }
        for i in 0..n {
            need[i as usize] = 0;
        }
        need[(n - 1) as usize] = aim;
        while l < r {
            let cur = zeroQueue[l as usize] as i32;
            l += 1;
            let supplement = max(need[cur as usize] - arr[cur as usize], 0);
            if graph[cur as usize].is_empty() && supplement > 0 {
                return false;
            }
            for next in graph[cur as usize].iter() {
                need[*next as usize] += supplement;
                help[*next as usize] -= 1;
                if help[*next as usize] == 0 {
                    zeroQueue[r as usize] = *next as i32;
                    r += 1;
                }
            }
        }
        true
    }
}

fn main() {
    let arr1 = [2, 0, 0, 1, 0];
    let convert1 = vec![vec![4, 2, 3], vec![1, 0], vec![2, 1]];
    println!("{}", maxValue(&arr1, &convert1));

    let arr2 = [100, 5, 5, 0];
    let convert2 = vec![vec![1, 0], vec![2, 0, 1], vec![3, 0, 1, 2]];
    println!("{}", maxValue(&arr2, &convert2));
}

在这里插入图片描述

c++完整代码如下：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 101;

int indegree[MAXN];
int help[MAXN];
int zeroQueue[MAXN];
int need[MAXN];
int n;

bool ok(vector<int>& arr, vector<vector<int>>& graph, int aim);

int maxValue(vector<int>& arr, vector<vector<int>>& convert) {
    n = arr.size();
    vector<vector<int>> graph(n);
    for (int i = 0; i < n; i++) {
        indegree[i] = 0;
    }
    for (auto& relation : convert) {
        for (int i = 1; i < relation.size(); i++) {
            graph[relation[0]].push_back(relation[i]);
            indegree[relation[i]]++;
        }
    }
    // arr[n-1] 初始就有100份
    // 101 ~ 整体累加和
    int l = arr[n - 1] + 1;
    int r = 0;
    for (int num : arr) {
        r += num;
    }
    int m = 0, ans = arr[n - 1];
    while (l <= r) {
        m = (l + r) / 2;
        if (ok(arr, graph, m)) {
            ans = m;
            l = m + 1;
        }
        else {
            r = m - 1;
        }
    }
    return ans;
}

bool ok(vector<int>& arr, vector<vector<int>>& graph, int aim) {
    int l = 0;
    int r = 0;
    for (int i = 0; i < n; i++) {
        help[i] = indegree[i];
        if (help[i] == 0) {
            zeroQueue[r++] = i;
        }
    }
    for (int i = 0; i < n; i++) {
        need[i] = 0;
    }
    need[n - 1] = aim;
    while (l < r) {
        int cur = zeroQueue[l++];
        int supplement = max(need[cur] - arr[cur], 0);
        if (graph[cur].empty() && supplement > 0) {
            return false;
        }
        for (int next : graph[cur]) {
            need[next] += supplement;
            if (--help[next] == 0) {
                zeroQueue[r++] = next;
            }
        }
    }
    return true;
}

int main() {
    vector<int> arr1 = { 2, 0, 0, 1, 0 };
    vector<vector<int>> convert1 = { { 4, 2, 3 }, { 1, 0 }, { 2, 1 } };
    cout << maxValue(arr1, convert1) << endl;

    vector<int> arr2 = { 100, 5, 5, 0 };
    vector<vector<int>> convert2 = { { 1, 0 }, { 2, 0, 1 }, { 3, 0, 1, 2 } };
    cout << maxValue(arr2, convert2) << endl;

    return 0;
}