网易笔试（凉）

Q1: 对于给定数组a（n<=1e6），每个元素（a[i]<=1e9）可拆成素数，求拆完后最多有多少个素数

分奇偶讨论即可
1、a[i]为偶，可最多拆成a[i]/2个素数（2）
2、为奇（>=3），1(1个3)+(a[i]-3)/2为最多，简单化简得a[i]/2

Q2：给定n（1~n），然后从中指定m个数为其子序列，求符合条件的n个数的最小字典序

// 双指针即可，一个数组为m指示的数，一个为n-m剩下的数，每次取最小
package main

import "fmt"

func main() {
    var n, m int
    sn, sm := []int{}, []int{}
    fmt.Scan(&n, &m)
    //vis := [100005]bool{}  才10万就爆内存，无法理解啊！！！
    vis := make([]bool, n+1)

    var v int
    for i := 1; i <= m; i++ {
        fmt.Scan(&v)
        sm = append(sm, v)
        vis[v] = true
    }
    for i := 1; i <= n; i++ {
        if !vis[i] {
            sn = append(sn, i)
        }
    }

    // 双指针
    ans := []int{}
    leftn, leftm := 0, 0
    for leftn < len(sn) && leftm < len(sm) {
        if sn[leftn] < sm[leftm] {
            ans = append(ans, sn[leftn])
            leftn++
        } else {
            ans = append(ans, sm[leftm])
            leftm++
        }
    }
    if leftn < len(sn) { // error for
        ans = append(ans, sn[leftn:]...)
    }
    if leftm < len(sm) {
        ans = append(ans, sm[leftm:]...)
    }
    // show
    fmt.Print(ans[0])
    for i := 1; i < len(ans); i++ {
        fmt.Printf(" %d", ans[i])
    }
}

Q3: N份（<=15）食物，各有其美味度（<=100000），求最少舍去食物以确保两人能获得价值美味度一样（不要求食物份数一样）

1、朴素解法：每份食物或不分（即舍去）或给A或给B，3^15=14348907，而且当时应该也是可以过的，只是程序中作为全局结果变量和局部变量混淆使用导致丢分
package main

import "fmt"

var ans int

func main() {
    var T, N int
    a := [15]int{}
    fmt.Scan(&T)
    for i := 1; i <= T; i++ {
        //ans, s := 1500000, 0  这里 ans 不能和 s 一起初始化，和全局变量混淆，导致 dfs 中 ans 更新失败！！！
        ans = 1500000
        s := 0
        fmt.Scan(&N)
        for k := 0; k < N; k++ {
            fmt.Scan(&a[k])
            s += a[k]
        }
        dfs(a[:N], s, 0, 0, 0) // 这里要限定 a 的大小为 N
        fmt.Println(ans)
    }
}

func dfs(a []int, s, v1, v2, i int) {
    if i == len(a) {
        if v1 == v2 {
            ans = min(ans, s-2*v1)
        }
        return
    }
    for k := i; k < len(a); k++ {
        dfs(a, s, v1, v2, k+1)
        dfs(a, s, v1+a[k], v2, k+1)
        dfs(a, s, v1, v2+a[k], k+1)
    }
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
2、416. 分割等和子集能处理等分情况，但是不等分怎么处理暂时不明白，后续更新！！！

Q4: POJ 3522 最大边与最小边差值最小的生成树，网上解法挺多的，还在理解细节中，后续补上！！！