跳至主要内容

简单的整数最小乘积的解法


给定 n 个整数,每次可以从剩下的整数中取走两个整数并计算这两个整数的积。

若该操作进行 m 次,求每次计算的积之和的最小值。
Input / 输入格式

有多组测试数据。第一行输入一个整数 T(约 30)代表测试数据组数,对于每组数据:

第一行输入两个整数 n 和 m(1≤n≤10​5​​, 0≤m≤​2​​n​​),它们的含义如题中所述。

第二行输入 n 个整数 a​1​​,a​2​​,⋯,a​n​​(0≤a​i​​≤10​4​​)表示给定的整数。
Output / 输出格式

每组数据输出一行一个整数,表示积之和的最小值。
Sample Input / 样例输入

3
4 2
1 3 2 4
3 1
2 3 1
4 0
1 3 2 4


Sample Output / 样例输出

10
2
0

 

Hint / 样例说明


对于第一组样例数据,答案是 1×4+3×2=10。

对于第二组样例数据,答案是 2×1=2。
















package main

import (
        "bufio"
        "fmt"
        "os"
        "sort"
        "strconv"
        "strings"
)

var data []int
var n int

func dodo(datastr string, m int) {

        if m == 0 {
                fmt.Printf("%d\n", 0)
                return
        }

        data = data[0:0]
        for _, s := range strings.Split(datastr, " ") {
                n, _ := strconv.Atoi(s)
                data = append(data, n)
        }

        sort.Ints(data)
        n = len(data)

        ret := 0
        for i := 0; i < m; i++ {
                ret += data[i] * data[m*2-i-1]
        }

        fmt.Printf("%d\n", ret)
}

func main() {
        reader := bufio.NewReader(os.Stdin)
        text, _ := reader.ReadString('\n')
        text = strings.TrimSpace(text)
        num, _ := strconv.Atoi(text)

        for i := 0; i < num; i++ {
                num, _ := reader.ReadString('\n')
                mn := strings.Split(num, " ")
                mstr := strings.TrimSpace(mn[1])
                m, _ := strconv.Atoi(mstr)

                str, _ := reader.ReadString('\n')
                str = strings.TrimSpace(str)

                dodo(str, m)
        }
}

评论

此博客中的热门博文