【备战秋招】每日一题:5月13日美团春招第四题:题面+题目思路 + C++/python/js/Go/java带注释

为了更好的阅读体检，为了更好的阅读体检，，可以查看我的算法学习博客第四题-沙堡

在线评测链接:P1289

题目描述

塔子哥在海边建了一个沙堡乐园。

里面有一个巨大的沙堡，塔子哥每年都会增加这个沙堡的层数，但也有一定的规律：

1、沙堡底层序号为 1 ；

2、沙堡的任何一个部分每年最多只能增加一个小沙堡(也可能不增加) ；

3、新建的小沙堡一定是独立的，没有和其他小沙堡连接(除了父亲沙堡)；

现在塔子哥准备了今年沙堡的示意图和明年沙堡的设计图，他想让你告诉他，第一座沙堡明年能否变成第二座沙堡。

输入描述

输入第一行为 T ，表示 T 组数据。( 1≤T≤10 )

对于每一组数据，包含4行：

第一行是第一座沙堡的个数：n ，第二行有 n-1 个数字(i=2,3,...,n) 表示第 i 个沙堡的是建在第 (i=2,3,...,n) 个沙堡上的。

第三行是第二座沙堡的个数：m ，第四行有 m-1 个数字 r_i(i=2,3,...,n) 表示第 i 个沙堡是建在第 (i=2,3,...,n)个沙堡上的。

()

输入保证两座沙堡的对应序号相同，即两座沙堡的共有点的父节点相同，且第二座包括第一座的所有节点。

输出描述

如果第一座明年有可能建成第二座，输出“yes”，否则输出”no”.

样例

输入

1
5
1 1 1 4
8
1 1 1 4 5 1 4

输出

yes

思路

模拟 + 排序

题目保证两座沙堡的对应序号相同。故前 n 个沙堡无需考虑是否相同的问题。

从明天的第 n + 1 个沙堡开始，为新增的沙堡，这块的沙堡要满足，所有沙堡的父亲沙堡编号都各不相同，所以沙堡的父亲编号都小于等于 n ，因为大于 n 的编号均为明天新增的小沙堡，其不可能作为其他沙堡的父亲沙堡。

为了方便判断是否有两个新增沙堡的父亲沙堡相同，将所有的新增沙堡按其父亲沙堡编号排序，如果两个沙堡的父亲沙堡编号相同，这两个沙堡在排序后必然相邻。

时间复杂度：O(n\log n) 排序的复杂度，因为合法的 m 最多是 2n

类似题目推荐

推荐几道排序相关的题目

LeetCode

1.合并两个有序数组

2.最大间距

Codefun2000

1. P1048. 华东师范大学保研机试-2022-整数排序

2. P1281 中国光大银行 2023.05.13-春招-第一题-泡泡排序

3. P1173 京东 2023.04.08-春招-第三题-构造排列

4. P1014 美团 2022.10.8-塔子玩游戏

代码

CPP

#include <bits/stdc++.h>
using namespace std;
​
void solve() {int n;cin >> n;vector<int> A;// 今天的沙堡for (int i = 1; i < n; ++i) {int j; cin >> j;j -= 1;A.emplace_back(j);}
​int m;cin >> m;vector<int> B;// 明天的沙堡for (int i = 1; i < m; ++i) {int j; cin >> j;j -= 1;B.emplace_back(j);}
​// 今天的沙堡数量必然小于等于明天的沙堡数量if (n > m) {cout << "no\n";return;}
​// 新增的沙堡的父亲沙堡编号全都是 < n 的，且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）// 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻sort(B.begin() + n - 1, B.end());for (int i = n - 1; i < B.size(); ++i) {if (B[i] >= n) {cout << "no\n";return;}if (i >= n && B[i] == B[i - 1]) {cout << "no\n";return;}}
​cout << "yes\n";
}
​
int main()
{int T = 1;cin >> T;while (T--) solve();
​return 0;
}

python

def solve():n = int(input())A = list(map(int, input().split()))# 今天的沙堡for i in range(n - 1):A[i] -= 1
​m = int(input())B = list(map(int, input().split()))# 明天的沙堡for i in range(m - 1):B[i] -= 1
​# 今天的沙堡数量必然小于等于明天的沙堡数量if n > m:print("no")return
​# 新增的沙堡的父亲沙堡编号全都是 < n 的，且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）# 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻B[n - 1:] = sorted(B[n - 1:])for i in range(n - 1, len(B)):if B[i] >= n:print("no")returnif i >= n and B[i] == B[i - 1]:print("no")return
​print("yes")
​
​
T = int(input())
for _ in range(T):solve()
​

Java

import java.util.*;
​
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int T = sc.nextInt();while (T-- > 0) {solve(sc);}}
​public static void solve(Scanner sc) {int n = sc.nextInt();List<Integer> A = new ArrayList<>();// 今天的沙堡for (int i = 1; i < n; ++i) {int j = sc.nextInt() - 1;A.add(j);}
​int m = sc.nextInt();List<Integer> B = new ArrayList<>();// 明天的沙堡for (int i = 1; i < m; ++i) {int j = sc.nextInt() - 1;B.add(j);}
​// 今天的沙堡数量必然小于等于明天的沙堡数量if (n > m) {System.out.println("no");return;}
​// 新增的沙堡的父亲沙堡编号全都是 < n 的，// 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）// 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻Collections.sort(B.subList(n - 1, B.size()));for (int i = n - 1; i < B.size(); ++i) {if (B.get(i) >= n) {System.out.println("no");return;}if (i >= n && B.get(i).equals(B.get(i - 1))) {System.out.println("no");return;}}
​System.out.println("yes");}
}

Go

package main
​
import ("bufio""fmt""os""sort""strconv"
)
​
func solve(scanner *bufio.Scanner) {n := nextInt(scanner)A := make([]int, n-1)// 今天的沙堡for i := 0; i < n-1; i++ {A[i] = nextInt(scanner) - 1}
​m := nextInt(scanner)B := make([]int, m-1)// 明天的沙堡for i := 0; i < m-1; i++ {B[i] = nextInt(scanner) - 1}
​// 今天的沙堡数量必然小于等于明天的沙堡数量if n > m {fmt.Println("no")return}
​// 新增的沙堡的父亲沙堡编号全都是 < n 的，// 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）// 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻sort.Ints(B[n-1:])for i := n - 1; i < len(B); i++ {if B[i] >= n {fmt.Println("no")return}if i >= n && B[i] == B[i-1] {fmt.Println("no")return}}
​fmt.Println("yes")
}
​
func nextInt(scanner *bufio.Scanner) int {scanner.Scan()n, _ := strconv.Atoi(scanner.Text())return n
}
​
func main() {scanner := bufio.NewScanner(os.Stdin)scanner.Split(bufio.ScanWords)
​T := nextInt(scanner)for i := 0; i < T; i++ {solve(scanner)}
}

Js

process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {input += data;return;
});
process.stdin.on('end', () => {const lines = input.trim().split('\n');let T = parseInt(lines[0]);let index = 1;while (T--) {let n = parseInt(lines[index++]);let A = lines[index++].split(' ').map(x => parseInt(x));// 今天的沙堡for (let i = 0; i < n-1; ++i) {A[i] -= 1;}
​let m = parseInt(lines[index++]);let B = lines[index++].split(' ').map(x => parseInt(x));// 明天的沙堡for (let i = 0; i < m-1; ++i) {B[i] -= 1;}
​// 今天的沙堡数量必然小于等于明天的沙堡数量if (n > m) {console.log("no");continue;}
​let is_no = false; 
​// 新增的沙堡的父亲沙堡编号全都是 < n 的，// 且新增的沙堡的父亲沙堡编号不能相同（每天一个沙堡只能新增一个小沙堡）// 将新增的沙堡的父亲编号排序，那么相同的父亲沙堡编号必然相邻B.slice(n - 1).sort((a, b) => a - b);for (let i = n - 1; i < B.length; ++i) {if (B[i] >= n) {console.log("no");is_no = true;break;}if (i >= n && B[i] === B[i - 1]) {console.log("no");is_no = true;break;}}if (!is_no) console.log("yes");}
});