题解 | #公司食堂#

Go的fmt输入老是超时，换成bufio的Scanner来输入就勉强可以通过测试。 时间复杂度应该是O(n)，三个切片来维护就好了。

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

func main() {
	var T, n, m int
	var sit, cus string
	in := bufio.NewScanner(os.Stdin)
	buf := make([]byte, 2e6)
	in.Buffer(buf, 2e6)
	in.Scan()
	T, _ = strconv.Atoi(in.Text())
	for ; T > 0; T-- {
		in.Scan()
		n, _ = strconv.Atoi(in.Text())
		in.Scan()
		sit = in.Text()
		in.Scan()
		m, _ = strconv.Atoi(in.Text())
		in.Scan()
		cus = in.Text()
		var one, zero, one_t []int
		for i := n - 1; i >= 0; i-- {
			if sit[i] == '0' {
				zero = append(zero, i+1)
			} else if sit[i] == '1' {
				one = append(one, i+1)
			}
		}
		for i := 0; i < m; i++ {
			if cus[i] == 'M' {
				if len(one) > 0 || len(one_t) > 0 {
					if len(one) > 0 && len(one_t) > 0 && one_t[0] < one[len(one)-1] {
						fmt.Printf("%d\n", one_t[0])
						one_t = one_t[1:]
					} else {
						if len(one) > 0 {
							fmt.Printf("%d\n", one[len(one)-1])
							one = one[:len(one)-1]
						} else {
							fmt.Printf("%d\n", one_t[0])
							one_t = one_t[1:]
						}
					}
				} else {
					fmt.Printf("%d\n", zero[len(zero)-1])
					one_t = append(one_t, zero[len(zero)-1])
					zero = zero[:len(zero)-1]
				}
			} else {
				if len(zero) > 0 {
					fmt.Printf("%d\n", zero[len(zero)-1])
					one_t = append(one_t, zero[len(zero)-1])
					zero = zero[:len(zero)-1]
				} else {
					if len(one) > 0 && len(one_t) > 0 && one_t[0] < one[len(one)-1] {
						fmt.Printf("%d\n", one_t[0])
						one_t = one_t[1:]
					} else {
						if len(one) > 0 {
							fmt.Printf("%d\n", one[len(one)-1])
							one = one[:len(one)-1]
						} else {
							fmt.Printf("%d\n", one_t[0])
							one_t = one_t[1:]
						}
					}
				}
			}
		}
	}
}