广联达0831笔试 题解

第一题：队列+map

原题：

一些粒子一个一个发到另一边，每个粒子拥有独一无二的编号，
有些粒子速度很快会提前到达，找出有几个粒子提前到达了。
输入n代表n个粒子，下面两行各n个数代表发送和接收时的编号。
样例：
输入：
5
1 2 3 4 5
2 3 4 1 5
输出：
3
解释：1在2 3 4前发射，但是2 3 4比1先到达

思路: 发送队列和接收队列, map存储发送队列中是否有提前到达的.

1. 如果发送队列和接收队列首个相同，那两个队列直接到下一个就好了。
2. 如果发送队列和接收队列首个不同，接收队列跳转到下一个，发送队列不变，计数器+1，标记map[revc[0]]=false，以便下次再遇到时直接跳过。
3. 重复1 2直到发送队列为空。

Golang：

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    start := make([]int, n)
    end := make([]int, n)
    //sm==true表示出发队列的这个是未到达的
    sm := make(map[int]bool)
    for i := 0; i < n; i++ {
        fmt.Scan(&start[i])
    }
    for i := 0; i < n; i++ {
        fmt.Scan(&end[i])
    }

    var res int
    for len(start) > 0 {
        if sm[start[0]] {
            if start[0] == end[0] {
                start = start[1:]
                end = end[1:]
            } else {
                res++
                //标记start中的，为已到达，以后直接跳过
                sm[end[0]] = false
                end = end[1:]
            }
        } else {
            start = start[1:]
        }
    }

    fmt.Println(res)
}

第二题：模拟

原题：

一排座位编号1..n，有m条规则，
每条规则是这样的座位区间[l,r]内最多有x个人坐，
问符合所有规则情况下，最多有多少人坐。
输入第一行两个数n m代表座位数和规则数，
下面m行每行有3个数分别代表l r x。
样例：
输入：
10 3
1 4 2
3 6 2
10 10 1
输出：
8
解释：3 4号座位是空的，其他坐满了

思路：寻求最多的座位使用，相当于寻求最少的座位未使用，即寻求最少的空白座位，我们当然希望一个空白座位属于多个区间内的，这样就可以复用空白座位，以达到最少空白座位的目的。

1. 创建记录所有规则的数据结构，这里使用数组+结构体。
2. 创建记录座位有哪些规则的数据结构，这里使用二维数组记录，第一维下标代表座位编号，每一维的数组代表遵顼的规则的下标（此下标是第一步记录规则的数组的下标）。
3. 找到座位中规则数量最多的座位（可以根据数组第二维的长度比较），访问其遵循的每个规则，让规则需要的空白座位减去1，若减去1后小于等于0，说明此规则已经完全满足，在第1步创建的规则数组中消去他（设为空）,并且结果+1.若规则需要的空白座位减去1后仍大于0，说明此规则还未满足，计数器+1以得知未满足的规则数。
4. 重复步骤3，每次更新未满足的规则数，直到未满足的规则数为0
5. 拿到了结果（最少需要的空白座位数），打印总座位数减去结果就是最多坐的人。

package main

import "fmt"

type Interval struct {
    start int
    end   int
    blank int //至少的空座位数量
}

func main() {
    //n个座位 m个规则
    var n, m int
    var x int
    fmt.Scan(&n, &m)
    //seats[i]表示这个座位属于哪几个规则区间，区间以下标存储
    seats := make([][]int, n+1)
    intervals := make([]Interval, m)
    for i := 0; i < m; i++ {
        fmt.Scan(&intervals[i].start)
        fmt.Scan(&intervals[i].end)
        fmt.Scan(&x)
        intervals[i].blank = intervals[i].end - intervals[i].start + 1 - x
        //对这个区间的座位加上规则
        for j := intervals[i].start; j <= intervals[i].end; j++ {
            seats[j] = append(seats[j], i)
        }
    }
    //每次取规则数最多的座位，视作空位，对应的规则空座数量减去1，当某个区间所需空格为0,去除掉他，所有区间都为0，结束
    var minTotalBlanks int
    leftRules := len(intervals)
    for leftRules > 0 {
        //找到规则最多的座位
        maxRules := 0
        maxRulesIdx := -1
        for i := 1; i < len(seats); i++ {
            if len(seats[i]) > maxRules {
                maxRules = len(seats[i])
                maxRulesIdx = i
            }
        }
        //对应的规则空座数量减去1
        leftRules = subBlank(seats[maxRulesIdx], intervals)
        seats[maxRulesIdx] = nil
        minTotalBlanks++
    }
    fmt.Println(n - minTotalBlanks)
}

func subBlank(idxs []int, intervals []Interval) int {
    var leftNums int
    for _, i := range idxs {
        intervals[i].blank--
        if intervals[i].blank > 0 {
            leftNums++
        }
    }
    return leftNums
}

/*

10 3
1 4 2
3 6 2
10 10 1

*/