首页 > 试题广场 >

名字的漂亮度

[编程题]名字的漂亮度

热度指数：151403 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

$\hspace{15pt}$ 对于给定由小写字母构成的字符串，定义字符串的“漂亮度”为该字符串中所有字母“漂亮度”的总和。
$\hspace{15pt}$ 每一个字母的“漂亮度”将由你来确定，具体规则如下：
$\hspace{23pt}\bullet\,$ 每一个字母的“漂亮度”为 $1$ 到 $26$ 之间的整数；
$\hspace{23pt}\bullet\,$ 没有两个字母的“漂亮度”相同。
$\hspace{15pt}$ 现在，你需要确定每个字母的“漂亮度”，以使得字符串的“漂亮度”最大。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

在一行上输入一个长度为  、仅由小写字母构成的字符串  。

输出描述:

对于每一组测试数据，输出一个整数，表示字符串的最大“漂亮度”。

示例1

输入

2
zhangsan
lisi

输出

192
101

说明

对于第一组测试数据，其中一种最优的分配方案是：
将字符  的漂亮度分配为  ；
将字符  的漂亮度分配为  ；
将字符  的漂亮度依次分配为  ；
其余字符随意分配；
最终，得到字符串的“漂亮度”为  。

对于第二组测试数据，其中一种最优的分配方案是：
将字符  的漂亮度分配为  ；
将字符  的漂亮度分配为  ；
将字符  的漂亮度分配为  ；
其余字符随意分配；
最终，得到字符串的“漂亮度”为  。

算法知识视频讲解

土土木木777

package main

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

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Scan()
	for scanner.Scan() {
		input := scanner.Text()
		if input == "" {
			return
		}

		charMap := map[byte]int{}

		for i := 0; i < len(input); i++ {
			charMap[input[i]]++
		}

		beautyList := []int{}

		for _, v := range charMap {
			beautyList = append(beautyList, v)
		}

		sort.Ints(beautyList)

		power := 26
		res := 0
		for i := len(beautyList) - 1; i >= 0; i-- {
			res += beautyList[i] * power
			power--
		}
		fmt.Println(res)
	}

}

发表于 2022-06-08 16:51:22 回复(0)

_Horace

从字符串按频率排序，时间复杂度O(n^2)，可以用堆排序优化

package main

import "fmt"

func main(){
    var n int
    fmt.Scanln(&n)
    for i := 0; i < n; i++{
        var s string
        fmt.Scanln(&s)
        fmt.Println(pretty(s))
    }
}

func pretty(s string)int{
    m := map[byte]int{}
    for i := 0; i < len(s); i++{
        m[s[i]] ++
    }
    // 从map中逐个找出最大的
    ans := 0
    cursor := 26
    for len(m) > 0{
        var maxV int
        var maxB byte
        for k, v := range m{
            if v > maxV{
                maxV = v
                maxB = k
            }
        }
        delete(m, maxB)
        ans += cursor * maxV
        cursor --
    }
    return ans
}

发表于 2022-05-17 17:41:19 回复(0)

rouroumaibing

package main

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

func main(){

    var param int
    var params []string
    
    fmt.Scan(&param)
    input := bufio.NewScanner(os.Stdin)
    for input.Scan() && param > 0{
        params = append(params, input.Text())
        param--
    }
    for loop:=0; loop< len(params); loop++{
        BeautValu(params[loop])
    }
}

func BeautValu(s string){
    var str []int
    var res int
    var mostBeaut = 26
    keyMap := make(map[string]int)
    for loop := 0 ;loop< len(s); loop++{
        keyMap[string(s[loop])]++
    }
    for _, value := range keyMap {
        str = append(str, value)
    }
    
    sort.Ints(str)
    
    for loop :=len(str) -1 ; loop >= 0 ; loop--{
        res += str[loop] * mostBeaut
        mostBeaut--
    }
    fmt.Println(res)
}

发表于 2021-10-21 20:17:17 回复(0)