跳至主要内容

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


给定 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)
        }
}

评论

此博客中的热门博文

老毛子路由器无线桥接问题

信道带宽:改成20M 关闭DHCP 服务器  关闭动态 (DHCP) 路由修改IP地址从192.168.123.1到192.168.1.114 无线 AP 工作模式:选择AP-Client+AP无线 AP-Client 角色:选择LAN bridge连上上级wifi done

路由器自身可能上不去网,执行:

route add default  gw 192.168.1.1

不过这种方式无法翻墙

//////////////////////////////////////////////////////////////

第二种方式
不改信道不关闭DHCP,保持网段是192.168.123.1无线 AP 工作模式:选择AP-Client+AP无线 AP-Client 角色:选择WAN连上上级wifi done

路由器可以翻墙,但是192.168.1.1的机器访问不了192.168.123.1的机器
解决方法:
在192.168.123.1的机器把想要访问的机器比如192.168.123.100设置DMZ主机,这样就可以访问了,在 192.168.1.1能看到分配的ip比如192.168.1.115

申请Oracle免费服务器

网址
https://www.oracle.com/cn/cloud/free/

首先注册账号,填国家china,地区一定要选好,因为免费的机器只能在home region,绑定手机,绑定信用卡。如果提示信用卡绑定失败,那么换个ip重试,比如开手机4G,或者挂VPN

账号申请了,开始申请机器,操作系统选centos7,比较简单,需要密钥
先生成
ssh-keygen -t rsa -N "" -b 2048 然后保存两个文件,id_rsa和id_rsa.pub,创建机器使用id_rsa.pub

机器创建好了,可以先telnet yourip 22试试ip是不是通的,如果不通,那么需要更换ip,比较绕
打开你的实例->左下角 附加的VNIC->查看详细->左下角 ip地址->编辑->改成没有公共ip->保存->再编辑,临时公共ip,或者预留ip。这样ip地址就更新了,刷几下就可以没有被ban。

然后用securecrt登陆,账号选择opc,会提示要pub,然后找到刚才的id_rsa.pub,连入成功。开始安装ss等软件。

安装好了,需要改一下防火墙配置
打开你的实例->虚拟云网络->左下角 安全列表->点进去->修改出入站规则

这时候telnet yourip ss端口,如果还是不行,在服务器执行sudo iptables -F,应该就可以了

一般缺点软件
sudo yum install lrzsz cmake gcc  gcc-c++ screen -y
最后
sudo yum update -y

要使用root
sudo su

js利用pako.js

首先引入js
<script src="pako.min.js"></script>

前端加上俩函数
    function unzip(b64Data){
        var strData   = atob(b64Data);
        // Convert binary string to character-number array
        var charData  = strData.split('').map(function(x){return x.charCodeAt(0);});
        // Turn number array into byte-array
        var binData   = new Uint8Array(charData);
        // // unzip
        var data    = pako.inflate(binData);
        // Convert gunzipped byteArray back to ascii string:
        strData   = new TextDecoder("utf-8").decode(data);
        alert(strData)
        return strData;
    }
    function zip(str){
         var binaryString = pako.gzip(encodeURIComponent(str), { to: 'string' })
         return btoa(binaryString);
    }

服务端先用 gzip然后base64
实际效果基本能节省一半
var b bytes.Bufferw := gzip.NewWriter(&b) defer w.Close() w.Write([]byte(data)) w.Flush() data = base64.StdEncoding.EncodeToString(b.Bytes())