|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- package main
- import "fmt"
- import "sync"
- type Node struct {
- h, w int
- }
- var (
- arr = make([]Node, 1e5)
- n, k int
- ch = make(chan int)
- judge = make(chan bool)
- wg sync.WaitGroup
- )
- func check() {
- tot, num := 0, <-ch
- for i := 0; i < n; i++ {
- tot += (arr[i].h / num) * (arr[i].w / num)
- if tot >= k {
- judge <- true
- return
- }
- }
- judge <- false
- }
- func main() {
- fmt.Scanf("%d %d", &n, &k)
- for i := 0; i < n; i++ {
- fmt.Scanf("%d %d", &arr[i].h, &arr[i].w)
- }
- wg.Add(1)
- go check()
- go func() {
- l, r := 1, 100000
- for l < r {
- mid := (l + r + 1) >> 1
- ch <- mid
- if <-judge {
- l = mid
- } else {
- r = mid - 1
- }
- }
- ch <- l
- wg.Done()
- }()
- fmt.Println(<-ch)
- wg.Wait()
- }
复制代码
输入:
2 10
5 6
6 5
应该输出2
本帖最后由 Brick_Porter 于 2022-9-30 23:09 编辑
看了你的代码,我发现第52行和第19行,main和check这两个goroutine都在从通道ch取值,也就是说这两个goroutine会发生争抢。整个程序执行过程中只要check没有抢到ch发送的值,那么tot, num := 0, <-ch这行代码就会一直阻塞从而引发死锁。
我想了一会儿,可以调换52、53这两行代码,如此一来可以保证暂时只有check可以从ch中取值,从而避免了19行的阻塞从而导致死锁问题。但这样做没有从根本上解决死锁问题。第一轮迭代程序第43行从judge中取值为false,所以r的值变为50000,1<50000成立,继续第二轮迭代。当程序执行到第42行的时候由于之前的check已经返回了,所以再没有其他goroutine从ch取值,这里又会阻塞从而引发死锁。要彻底解决这个死锁问题,就需要重写check这个函数了,不能让它提前返回。
我的修改如下: - package main
- import (
- "fmt"
- "sync"
- )
- type Node struct {
- h, w int
- }
- var (
- arr = make([]Node, 3)
- n, k int
- ch = make(chan int)
- result = make(chan int) // 保存结果,与ch分开,避免共用
- judge = make(chan bool)
- wg sync.WaitGroup
- )
- func check() {
- tot := 0
- loop:
- for num := range ch {
- for i := 0; i < n; i++ {
- tot += (arr[i].h / num) * (arr[i].w / num)
- if tot >= k {
- judge <- true
- continue loop
- }
- }
- judge <- false
- }
- }
- func main() {
- fmt.Scanf("%d %d\n", &n, &k)
- for i := 0; i < n; i++ {
- fmt.Scanf("%d %d\n", &arr[i].h, &arr[i].w)
- }
- l, r := 1, 100000
- wg.Add(1)
- go check()
- go func() {
- for l < r {
- mid := (l + r + 1) >> 1
- ch <- mid
- if <-judge {
- l = mid
- } else {
- r = mid - 1
- }
- fmt.Printf("l: %v, r: %v, mid: %v\n", l, r, mid)
- }
- close(ch)
- wg.Done()
- result <- l
- }()
- wg.Wait()
- fmt.Println(<-result)
- }
复制代码
|
|