20231117上机编程[高可靠在线视频]-526互联

某电信公司推出高可靠的在线视频业务。为了保证可靠性，公司针对不同视频类型，准备了不同的专用网络通道，并对指定视频类型服务进行通道分配。一个用户在一个时段只能使用一个视频服务，可以多次申请。请实现以下功能：

VideoService(int[] channels, int[] charge) ：初始化系统
- channels[i]表示视频类型为i的初始可用通道个数。charge[i] 表示视频类型为i的单位时间费用。
- 视频类型仅为：标清视频、高清视频、超清视频，分别用 0、1、2 表示，且对应的带宽从低到高。
allocateChannel(int time, int userId, int videoType) ：在time时刻，用户userId申请使用videoType类型的视频服务。注：计费依照该次申请的视频类型，而非实际占用通道的视频类型。
- 如果当前视频类型videoType有可用通道，则占用一个通道，并返回 true；
- 否则，依次寻找更高带宽的通道，如果有可用，则占用该类型的一个通道，并返回 true；如果仍找不到可用通道，则返回 false 。
- freeChannel(int time, int userId) ：在time时刻，用户userId申请停止在使用的视频服务：
  - 如果userId正在使用视频服务，则停止该服务并释放所占用的通道，并返回该次服务的费用（可能为 0）；否则，返回 -1 。
  - 当有通道释放时，如果之前有其他用户因为申请时通道不足而占用了更高带宽的通道，且占用带宽高于释放通道的带宽、所申请带宽不高于释放通道的带宽，则选择一个用户进行降级使用该释放通道。
    - 优先选择占用带宽最高的用户；如果还有多个，则选择其中 userId 最小的。
    - 注意：降级所释放通道需要重复上述过程。
queryChannel(int userId)：查询用户 userId正在使用服务所占用通道的视频类型；若用户不存在或已经停服，则返回 -1。

注：用例保证，1）接口调用中的 time 递增； 2）同一用户停止当前所使用的视频服务后，才会再次申请。

输入

每行表示一个函数调用，初始化函数仅首行调用一次，累计函数调用不超过1000次。

l 1 <= channels[i] <= 1000, 1 <= charge[i] <= 100, channels.length == charge.length == 3

l 1 <= time <= 1000, 1 <= userId <= 1000

l 输入保证videoType的取值仅为 0、1、2

输出

答题时按照函数/方法原型中的要求（含返回值）进行实现，输出由框架完成（其中首行固定输出 null）

样例1

输入：

VideoService([8, 1, 1], [10, 15, 30])

allocateChannel(3, 107, 1)

allocateChannel(3, 108, 1)

allocateChannel(5, 110, 1)

queryChannel(108)

freeChannel(13, 108)

输出：

null

true

false

150

解释：

VideoService([8, 1, 1], [10, 15, 30])：标清视频、高清视频、超清视频的初始可用通道个数分别为 8、1、1；单位时间费用分别为10、15、30。
allocateChannel(3, 107, 1)：时刻3，用户107申请高清视频服务，返回true。
allocateChannel(3, 108, 1)：时刻3，用户108申请高清视频服务，由于高清视频的可用通道已全被占用，但超清视频还有通道可用，因此该用户实际占用超清通道，返回true。
allocateChannel(5, 110, 1)：时刻5，用户110申请高清视频服务，由于高清视频和超清视频的可用通道已全被占用，返回false。
queryChannel(108)：查询用户108正在使用服务所占用通道的视频类型，返回2（即超清视频）。
freeChannel(13, 108)：时刻13，用户108停止使用视频服务，该次使用时长为10，返回计费为15*10=150。注意虽然该用户占用超清通道，但计费时仍按照其申请的高清视频类型计费。

样例2

输入：

VideoService([1, 1, 2], [5, 10, 20])

allocateChannel(1, 100, 0)

allocateChannel(1, 101, 0)

allocateChannel(2, 102, 0)

allocateChannel(4, 103, 0)

freeChannel(6, 100)

queryChannel(102)

freeChannel(7, 103)

allocateChannel(7, 104, 1)

freeChannel(8, 102)

queryChannel(104)

输出：

null

true

解释：

最初4个allocateChannel操作，4个用户都申请标清视频服务，但用户101占用高清通道。用户102和用户103占用超清通道。
freeChannel(6, 100)：时刻6，用户100停止服务，释放出标清通道。此时101、102、103三个用户都可以降到标清通道。根据规则，优先选择占用带宽最高的用户102和103，再从这两个用户中优先选择 userId 最小的用户102降到标清通道。
freeChannel(8, 102)：时刻8，用户102停止服务，释放出标清通道；用户101降到标清通道，又释放出高清通道；然后用户104从超清通道降到用户101刚释放的高清通道。

题目理解：

这道题需要设计一个视频服务系统，为用户提供视频服务，并且需要分配和释放通道。

1) 视频类型有三种类型：标清、高清、超清，申请时如果低清晰度可用通道不足，可占用更高带宽的可用通道，只用付申请类型的费用。

2) 在释放通道x后，其他用户因为申请通道 m 不足而占用了更高带宽的通道n, 若满足 n > x && m <= x 则需要降级，而且有可能触发连锁降级。

以样例2为例，连锁降级如下图所示：

时刻8触发了连锁降级。注意：时刻8没有首先把104降级的原因是，104申请的视频类型是1，比102释放的0高；等到102释放出1后，104申请的类型和释放的相等，就可以降级到1了。

思路解析：

1) 设计建模

系统的初始通道数量和单位时间费用和具体用户无关，存在VideoService中即可。

每个用户的申请信息，可以单独创建一个User类（可维护性更好），也可以全部记录在VideoService中。

2) 连锁降级的实现方法

有两种方法：

l 递归降级：递归结束条件是找不到需要降级的用户，或者用户释放的占用通道已经是超清通道

l 循环降级：循环退出条件是找不到需要降级的用户，或者用户释放的占用通道已经是超清通道

给的参考1：

package main

import (
    "fmt"
)

type VideoService struct {
    channels []int
    charge   []int
    used     map[int][]int
}

func NewVideoService(channels []int, charge []int) *VideoService {
    return &VideoService{
        channels: channels,
        charge:   charge,
        used:     make(map[int][]int),
    }
}

func (vs *VideoService) AllocateChannel(time, userID, videoType int) bool {
    for i := videoType; i < len(vs.channels); i++ {
        if vs.channels[i] == 0 {
            continue
        }
        vs.used[userID] = []int{i, time, videoType, userID}
        vs.channels[i]--
        return true
    }
    return false
}

func (vs *VideoService) FreeChannel(time, userID int) int {
    if arr, ok := vs.used[userID]; ok {
        delete(vs.used, userID)
        vs.channels[arr[0]]++
        videoType := arr[0]
        for {
            id := vs.getUserID(videoType, vs.used)
            if id == -1 {
                break
            }
            nextVideoType := vs.used[id][0]
            vs.channels[nextVideoType]++
            vs.channels[videoType]--
            vs.used[id][0] = videoType
            videoType = nextVideoType
        }
        return vs.charge[arr[2]] * (time - arr[1])
    }
    return -1
}

func (vs *VideoService) getUserID(videoType int, values map[int][]int) int {
    for _, arr := range values {
        if arr[0] > arr[2] && arr[2] <= videoType && arr[0] > videoType {
            return arr[3]
        }
    }
    return -1
}

func (vs *VideoService) QueryChannel(userID int) int {
    if arr, ok := vs.used[userID]; ok {
        return arr[0]
    }
    return -1
}

func main() {
    channels := []int{10, 10, 10}
    charge := []int{1, 2, 3}

    videoService := NewVideoService(channels, charge)

    fmt.Println(videoService.AllocateChannel(1, 1, 0)) // true
    fmt.Println(videoService.AllocateChannel(2, 2, 1)) // true
    fmt.Println(videoService.AllocateChannel(3, 3, 2)) // true
    fmt.Println(videoService.AllocateChannel(4, 4, 0)) // false

    fmt.Println(videoService.QueryChannel(1)) // 0
    fmt.Println(videoService.QueryChannel(2)) // 1
    fmt.Println(videoService.QueryChannel(3)) // 2
    fmt.Println(videoService.QueryChannel(4)) // -1

    fmt.Println(videoService.FreeChannel(5, 2))  // 6
    fmt.Println(videoService.FreeChannel(6, 3))  // 9
    fmt.Println(videoService.FreeChannel(7, 10)) // -1

    fmt.Println(videoService.QueryChannel(2)) // -1
    fmt.Println(videoService.QueryChannel(3)) // -1
}

View Code

参考2：

package main

import (
    "fmt"
    "sort"
)

type User struct {
    userId        int
    startTime     int
    targetChannel int
    realChannel   int
}

type VideoService struct {
    channels []struct {
        availChannelCount int
        charge            int
    }
    users []User
}

func NewVideoService(channels []int, charge []int) *VideoService {
    vs := &VideoService{
        channels: make([]struct {
            availChannelCount int
            charge            int
        }, len(channels)),
        users: []User{},
    }
    for i := 0; i < len(channels); i++ {
        vs.channels[i].availChannelCount = channels[i]
        vs.channels[i].charge = charge[i]
    }
    return vs
}

func (vs *VideoService) AllocateChannel(time, userId, videoType int) bool {
    for i := videoType; i <= 2; i++ {
        if vs.channels[i].availChannelCount > 0 {
            vs.channels[i].availChannelCount--
            vs.users = append(vs.users, User{
                userId:        userId,
                startTime:     time,
                targetChannel: videoType,
                realChannel:   i,
            })
            return true
        }
    }
    return false
}

func (vs *VideoService) FreeChannel(time, userId int) int {
    index := -1
    for i, user := range vs.users {
        if user.userId == userId {
            index = i
            break
        }
    }
    if index == -1 {
        return -1
    }
    freeUser := vs.users[index]
    vs.users = append(vs.users[:index], vs.users[index+1:]...)
    totalCharge := (time - freeUser.startTime) * vs.channels[freeUser.targetChannel].charge
    vs.downGradeChannel(freeUser.realChannel)
    return totalCharge
}

func (vs *VideoService) downGradeChannel(videoType int) {
    upgradedUsers := []User{}
    for _, user := range vs.users {
        if user.realChannel > videoType && user.targetChannel <= videoType {
            upgradedUsers = append(upgradedUsers, user)
        }
    }
    if len(upgradedUsers) == 0 {
        vs.channels[videoType].availChannelCount++
    } else {
        sort.Slice(upgradedUsers, func(i, j int) bool {
            if upgradedUsers[i].realChannel > upgradedUsers[j].realChannel {
                return true
            } else if upgradedUsers[i].realChannel < upgradedUsers[j].realChannel {
                return false
            } else {
                return upgradedUsers[i].userId < upgradedUsers[j].userId
            }
        })
        downgradeUser := upgradedUsers[0]
        typ := downgradeUser.realChannel
        downgradeUser.realChannel = videoType
        vs.downGradeChannel(typ)
    }
}

func (vs *VideoService) QueryChannel(userId int) int {
    for _, user := range vs.users {
        if user.userId == userId {
            return user.realChannel
        }
    }
    return -1
}

func main() {
    channels := []int{10, 10, 10}
    charge := []int{1, 2, 3}

    videoService := NewVideoService(channels, charge)

    fmt.Println(videoService.AllocateChannel(1, 1, 0)) // true
    fmt.Println(videoService.AllocateChannel(2, 2, 1)) // true
    fmt.Println(videoService.AllocateChannel(3, 3, 2)) // true
    fmt.Println(videoService.AllocateChannel(4, 4, 0)) // false

    fmt.Println(videoService.QueryChannel(1)) // 0
    fmt.Println(videoService.QueryChannel(2)) // 1
    fmt.Println(videoService.QueryChannel(3)) // 2
    fmt.Println(videoService.QueryChannel(4)) // -1

    fmt.Println(videoService.FreeChannel(5, 2))  // 6
    fmt.Println(videoService.FreeChannel(6, 3))  // 9
    fmt.Println(videoService.FreeChannel(7, 10)) // -1

    fmt.Println(videoService.QueryChannel(2)) // -1
    fmt.Println(videoService.QueryChannel(3)) // -1
}

View Code

待补充的

// 答题框内的代码仅为待实现代码，执行或提交代码时，仅包含待实现部分，不要包含其它代码（也不要包含 package main）。
// 判题时CodeCheck/Cmetrics等工具也仅扫描待实现部分。
// 若需要完整框架用于本地调试，请点击答题框上面的“下载完整框架代码”进行下载。
type videoService struct {
    channels []int
    charges []int
    oldUse map[int][]int
    realUse map[int]int
}

func construct(channels []int, charge []int) *videoService {
    return &videoService{
        channels, 
        charge,
        make(map[int][]int),
        make(map[int]int),
    }
}

func (sys *videoService) allocateChannel(time, userId, videoType int) bool {  
    applyChan := make([]int, 2)
    applyChan[0] = videoType
    applyChan[1] = time
    sys.oldUse[userId] = applyChan  
    for i:=videoType; i<=2; i++ {
        chanCount := sys.channels[i]
        if chanCount > 0 { 
            sys.realUse[userId] = i 
            sys.channels[i] --
            return true
        }
    }  
    return false
}

func (sys *videoService) freeChannel(time, userId int) int {
    oldApply, ok := sys.oldUse[userId]
    if !ok {
        return -1
    }
    oldChan := oldApply[0]
    oldTime := oldApply[1]
    oldCharge := sys.charges[oldChan] 
    realApplyChan, _ := sys.realUse[userId] 
    ansCharge := (time - oldTime) * oldCharge
    sys.channels[realApplyChan] ++ 
    fmt.Println(sys)
    delete(sys.oldUse, userId)
    delete(sys.realUse, userId)  
    // 循环降级 申请值
    
    return ansCharge
}

func (sys *videoService) queryChannel(userId int) int {
    realApply,ok := sys.realUse[userId]
    if !ok {
        return -1
    }
    fmt.Println(sys)
    return realApply
}

View Code

输入：

VideoService([1, 1, 1], [50, 60, 70])
allocateChannel(12, 6, 0)
allocateChannel(30, 90, 1)
allocateChannel(410, 890, 1)
freeChannel(500, 6)
queryChannel(890)
freeChannel(500, 90)
queryChannel(890)


输出：

null
true
true
true
24400
2
28200
1