首页 > 试题广场 >

火眼金睛

[编程题]火眼金睛

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

现在我们需要查出一些作弊的问答社区中的ID，作弊有两种：1.A回答了B的问题，同时B回答了A的问题。那么A和B都是作弊。2.作弊ID用户A和作弊ID用户B同时回答了C的问题，那么C也是作弊。已知每个用户的ID是一串数字，一个问题可能有多个人回答。

输入描述:

每组数据第一行为总问题数N(N小于等于200000)，第二行开始每行一个问题，第一个数字为提问人ID，第二个数字为回答人数，后面则为所有回答人的ID。(ID均为0-1000000的整数)

输出描述:

第一行为作弊ID数量，第二行开始为从小到大的每行一个作弊ID。

示例1

输入

输出

3
1 2 3

算法知识视频讲解

cloud_yellow

同样的代码本地IDE通过了但是在这上面总提示越界，扔讨论里看看。

做个map然后出题人是key，答题人是value切片。

先检查答题人出的提里是否有出题人的回答，如果有的话就把这俩都计入作弊ID的集合里。

然后检查还没被列为作弊人的题目里是否有两个以上的作弊者来答题，如果有那就把他也列入作弊者，重复检查直到没有新增作弊者。

按要求输出作弊者数量和排序后id。

package main

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

func main() {
	n := 0

	fmt.Scanln(&n)

	record := make(map[string][]string)

	for ; n > 0; n-- {
		res := bufio.NewReader(os.Stdin)
		read, _ := res.ReadString('\n')
		read = strings.TrimSpace(read)

		sli := strings.Split(read, " ")
		leng, _ := strconv.Atoi(sli[1])
        // leng :=0
		record[sli[0]] = make([]string, leng)

		for i := 2; i < len(sli); i++ {
			record[sli[0]][i-2] = sli[i]
            // record[sli[0]] = append(record[sli[0]], sli[i])
		}

	}
	cheatId := []string{}
	//相互回答检查
	for k, v := range record {
		for j := 0; j < len(v); j++ {
			if _, ok := record[v[j]]; ok {
				for _, val := range record[v[j]] {
					if val == k {
						bol := ""
						for _, valCheck := range cheatId {
							if valCheck == k {
								bol += "k"
							}

							if valCheck == v[j] {
								bol += "v"
							}
						}
						switch {
						case bol == "k":
							cheatId = append(cheatId, v[j])
						case bol == "v":
							cheatId = append(cheatId, k)
						case bol == "kv" || bol == "vk":
							continue
						case bol == "":
							cheatId = append(cheatId, k, v[j])
						}
						// cheatId = append(cheatId, k,v[j])
					}
				}
			}
		}
	}

	//共同回答检查
	for {
		addCount := 0

		for k1, v1 := range record {
			//判定是否已经列入作弊者
			cheatCheckBol := false
			for _, cheatCheck := range cheatId {
				if k1 == cheatCheck {
					cheatCheckBol = true
					break
				}
			}

			if cheatCheckBol {
				continue
			}

			checkCount := 0
			for _, val := range v1 {
				for _, valCheck := range cheatId {
					if val == valCheck {
						checkCount++
					}
				}

			}

			if checkCount >= 2 {
				cheatId = append(cheatId, k1)
				addCount++
			}
		}

        if addCount == 0{
            break
        }

	}

    sort.Strings(cheatId)
    ans := cheatId[0]
    for i:=1;i<len(cheatId);i++{
        ans = ans + " " + cheatId[i]
    }
    fmt.Println(ans)

}

发表于 2023-08-06 13:34:37 回复(0)