严选的快递员每天需要送很多个包裹，在货物装车后，需要开着电动车先到0号用户家。送完货后从0号出发，再送到1号用户。然后快递员可以从1号直接到2号用户家，完成送货。但有时候由于路不通的原因，需要先折返回0号，再去2号，如此循环，完成送货。
由于路况复杂，每个用户家只有一条路通往附近的其他一户邻居家，假设每条通路都是1公里。另外快递员的电动车的电是有限的，最多只能开有限的k公里。现在快递员已经在0号用户家送完快递，问快递员最多可以送多少个不重复的用户
[编程题]送快递
- 热度指数：354 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
- 算法知识视频讲解
输入描述:
输入包括两行,第一行包括两个正整数n(2 ≤ n ≤ 1000)和k(1 ≤ k ≤ 3000),表示用户家个数和快递员电动车剩余还能够行使的路程。第二行包括n-1个整数，定义该数组为S，对于每个数组下标 i (0 ≤ i ≤ n - 2)，第i+1号用户跟S[i]号用户有一条道路连接。（参见下方样例和上图）
输出描述:
输出一个整数，表示快递员该次累计最多可以送几个用户
示例1
输入
6 3 0 0 2 3 3
输出
4
说明
通路情况如上图所示，走 0->2->3->4 的路线，或者走0->2->3->5的路线，电动车刚好再送3次快递，加一开始的0号用户累计是送了4个快递。
示例2
输入
5 2 0 1 2 3
输出
3
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
String[] nk = s.nextLine().split(" ");
String[] link = s.nextLine().split(" ");
s.close();
int k = Integer.parseInt(nk[1]);
int dpt = dpt(link);
if (dpt >= k) {
System.out.println(k + 1);
} else {
System.out.println(Math.min(link.length + 1, dpt + 1 + (k - dpt) / 2));
}
}
public static int dpt(String[] link) {
Node[] nodes = new Node[link.length + 1];
nodes[0] = new Node(0);
int ind = 0;
for (String parrent : link) {
Node pn = nodes[Integer.parseInt(parrent)];
nodes[++ind] = new Node(pn.dpt + 1);
}
ind = 0;
for (Node node : nodes) {
ind = Math.max(ind, node.dpt);
}
return ind;
}
}
class Node {
public int dpt = 1;
public Node(int dpt) {
this.dpt = dpt;
}
}
发表于 2021-08-21 09:19:07
回复(1)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] str = sc.nextLine().split(" ");
int n = Integer.parseInt(str[0]);
int k = Integer.parseInt(str[1]);
String[] num = sc.nextLine().split(" ");
int[] s = new int[num.length];
for (int i = 0; i < num.length; i++) {
s[i] = Integer.parseInt(num[i]);
}
boolean[][] dp = new boolean[n][n];
for (int i = 1; i < n; i++) {
dp[s[i-1]][i] = true;
dp[i][s[i-1]] = true;
}
int depth = depthOfTree(dp);
if (k < depth) {
System.out.println(k + 1);
}else {
int res = Math.min(n,depth + (k - depth + 1) / 2);
System.out.println(res);
}
}
/*
利用树的邻接表的层次遍历求出树的深度
*/
public static int depthOfTree(boolean[][] adjacentMatrix) {
LinkedList<Integer> queue = new LinkedList<>();
int nodeNumber = adjacentMatrix.length;
boolean[] visited = new boolean[nodeNumber];
int depth = 0;
queue.add(0);
visited[0] = true;
int layerNodes = 1;
int nextLayerNodes = 0;
while (queue.size() != 0) {
while (layerNodes-- > 0) {
int curNode = queue.poll();
for (int i = 1; i < nodeNumber; i++) {
if (adjacentMatrix[curNode][i] && !visited[i]) {
nextLayerNodes ++;
visited[i] = true;
queue.add(i);
}
}
}
layerNodes = nextLayerNodes;
nextLayerNodes = 0;
depth++;
}
return depth;
}
}
发表于 2021-07-30 16:58:09
回复(0)
提供一个纯暴力解法，能通过7个用例。 想不出来贪心的可以尝试，好歹能拿分而且容易理解点。。
核心思路：DFS直接纯暴力搜索，无路可走时就走回头路，因此每次dfs时要记录前驱节点，用一个set记录已经走过的节点，由于编号不重复，所以每次电量用完，set中的元素个数就是遍历过的节点个数。
import java.util.*;
public class Main {
static Map> map = new HashMap();
static int res = 0;
public static void main(String[] args){
Scanner cin = new Scanner(System.in);
String s1 = cin.nextLine();
String[] strs1 = s1.split(" ");
int n = Integer.parseInt(strs1[0]);
int k = Integer.parseInt(strs1[1]);
String s2 = cin.nextLine();
String[] strs2 = s2.split(" ");
//用map构造邻接表
for(int i = 0; i < strs2.length; i++){
int node = Integer.parseInt(strs2[i]);
List list1 = map.getOrDefault(node, new ArrayList());
list1.add(i + 1);
map.put(node, list1);
List list2 = map.getOrDefault(i + 1, new ArrayList());
list2.add(node);
map.put(i + 1, list2);
}
//从节点0开始暴力搜索，注意0的前驱节点设置为-1,因为0节点的位置无法再回头
visited.add(0);
dfs(-1, 0, k);
System.out.println(res);
}
static Set visited = new HashSet();
public static void dfs(int prev, int cur, int k){
//电量用完，visited中存的元素个数即为现在已遍历过的节点个数
if(k == 0){
res = Math.max(res, visited.size());
return;
}
//遍历当前节点cur的每个邻居
for(int next : map.get(cur)){
//走过的节点不再走
if(visited.contains(next)){
continue;
}
//邻居可走，则标记已走过，并dfs继续走
visited.add(next);
dfs(cur, next, k - 1);
visited.remove(next);
}
//当前节点的所有邻居都不可走，则折返回头走
//注意，如果prev等于-1，说明当前在0节点，邻居都已经走完了，也没法再回头走，直接结束dfs
if(prev != -1){
dfs(cur, prev, k - 1);
}
}
}
编辑于 2022-03-26 15:07:16
回复(1)
方法：树形DP
DP[u] [i] [0]表示以u为根，走了i步，最后不回到u能经过的节点数
DP[u] [i] [1]表示以u为根，走了i步，最后回到u能经过的节点数
走了i步，最后不回到u，那么最后肯定是在走某个子树，设在子树v中走了j步，最后停留在子树v，那么还有i - 1 - j步是在其他子树里走的，然后回到u，再去走v
DP[u] [i] [0] = max(DP[u] [i - j - 1] [1] + DP[v] [j] [0])
还有一种情况是，最后停留在其他子树，先走子树v，再返回到u，再走其他子树
DP[u] [i] [0] = max(DP[u] [i - j - 2] [0] + DP[v] [j] [1])
走了i步，最后回到u，那么某个子树v走j步返回，其他子树走i - 1 - j - 1 = i - j - 2步返回
DP[u] [i] [1] = max(DP[u] [i - j - 2] [1] + DP[v] [j] [1])
注意子树可以走的最大步数是子树边总数 * 2，边数即子树结点数 - 1，所以要用一次dfs，用数组保存子树结点数
DP的初始状态为走0步的情况，dp[i] [0] [1] = 1;dp[i] [0] [0] = 1;
走0步即停留在某个子树根处，看状态转移方程，已经考虑了u到v的一步，所以dp[i] [0] [0]也要为1，表示停留在子树根没动
import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
/**
DP[u] [i] [0]表示以u为根，走了i步，最后不回到u能经过的节点数
DP[u] [i] [1]表示以u为根，走了i步，最后回到u能经过的节点数
走了i步，最后不回到u，那么最后肯定是在走某个子树，设在子树v中走了j步，最后停留在子树v，那么还有i - 1 - j步是在其他子树里走的，然后回到u，再去走v
DP[u] [i] [0] = max(DP[u] [i - j - 1] [1] + DP[v] [j] [0])
还有一种情况是，最后停留在其他子树，先走子树v，再返回到u，再走其他子树
DP[u] [i] [0] = max(DP[u] [i - j - 2] [0] + DP[v] [j] [1])
走了i步，最后回到u，那么某个子树v走j步返回，其他子树走i - 1 - j - 1 = i - j - 2步返回
DP[u] [i] [1] = max(DP[u] [i - j - 2] [1] + DP[v] [j] [1])
子树可以走的最大步数是子树边总数 * 2, 边数即子树结点数 - 1
*/
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
// 注意 hasNext 和 hasNextLine 的区别
while (in.hasNextInt()) { // 注意 while 处理多个 case
int n = in.nextInt();
int k = in.nextInt();
int i, j;
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
for (i = 0; i < n; i++) {
list.add(new ArrayList<>());
}
for (i = 0; i < n - 1; i++) {
list.get(in.nextInt()).add(i + 1);
}
int[][][] dp = new int[n][k + 1][2];
for (i = 0; i < n; i++) {
dp[i][0][1] = 1;
dp[i][0][0] = 1;
}
int[] count = new int[n];
getNum(0, list, count);
int ans = 0;
ans = Math.max(getDp(0, k, list, dp, count).dp0, getDp(0, k, list, dp, count).dp1);
System.out.println(Math.min(n, ans));
}
}
static int getNum(int u, ArrayList<ArrayList<Integer>> list, int[] count) {
int c = 1;
for (int i = 0; i < list.get(u).size(); i++) {
c += getNum(list.get(u).get(i), list, count);
}
count[u] = c;
return c;
}
static Val getDp(int u, int i, ArrayList<ArrayList<Integer>> list, int[][][] dp, int[] count) {
if (dp[u][i][0] != 0 && dp[u][i][1] != 0) {
return new Val(dp[u][i][0], dp[u][i][1]);
}
int p, q;
for (p = 0; p < list.get(u).size(); p++) {
int v = list.get(u).get(p);
for (q = 0; q <= Math.min(i - 1, (count[v] - 1) * 2); q++) {
dp[u][i][0] = Math.max(getDp(u, i - q - 1, list, dp, count).dp1 + getDp(v, q, list, dp, count).dp0, dp[u][i][0]);
}
for (q = 0; q <= Math.min(i - 2, (count[v] - 1) * 2); q++) {
dp[u][i][0] = Math.max(getDp(u, i - q - 2, list, dp, count).dp0 + getDp(v, q, list, dp, count).dp1, dp[u][i][0]);
}
for (q = 0; q <= Math.min(i - 2, (count[v] - 1) * 2); q++) {
dp[u][i][1] = Math.max(getDp(u, i - q - 2, list, dp, count).dp1 + getDp(v, q, list, dp, count).dp1, dp[u][i][1]);
}
}
return new Val(dp[u][i][0], dp[u][i][1]);
}
static class Val {
int dp0;
int dp1;
public Val(int dp0, int dp1) {
this.dp0 = dp0;
this.dp1 = dp1;
}
}
}
发表于 2022-12-20 22:58:45
回复(0)
#include<bits/stdc++.h>
#include<stack>
#include<vector>
#include<unordered_set>
using std::endl;
typedef std::vector< std::vector<int> > ErweiMatrix;
typedef std::unordered_set<int> Hashset;
int FanHuiXiaoBiao(std::vector<int> ShuZu, int Zhi) {
int XiaoBiao = -1;
for (int counter_1 = 0;counter_1 < ShuZu.size();counter_1++) {
if (ShuZu[counter_1] == Zhi) {
XiaoBiao = counter_1;
break;
}
}
return XiaoBiao;
}
bool ISLianJie(int Node_1, int Node_2, ErweiMatrix NodeArray) {
for (int nextNodes : NodeArray[Node_1]) {
if (nextNodes == Node_2) {
return true;
break;
}
}
return false;
}
int GetMaxIndex_XianZhi(std::vector<int> ShuZu, int XianZhi) {
int GetMaxValue = 0;
for (int counter_1 = 0;counter_1 < ShuZu.size();counter_1++) {
if ((ShuZu[counter_1] > 0) && ((XianZhi - 2 * ShuZu[counter_1]) >= 0)) {
GetMaxValue = ShuZu[counter_1] > GetMaxValue ? ShuZu[counter_1] : GetMaxValue;
}
}
return FanHuiXiaoBiao(ShuZu, GetMaxValue);
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int DianShu = 0;
int MP = 0;
std::cin >> DianShu >> MP;
std::vector<int> input(DianShu - 1);
for (int counter_1 = 0;counter_1 < DianShu - 1;counter_1++) {
std::cin >> input[counter_1];
}
ErweiMatrix NodeArray(DianShu);
for (int counter_1 = 0;counter_1 < DianShu - 1;counter_1++) {
NodeArray[input[counter_1]].push_back(counter_1 + 1);
NodeArray[counter_1 + 1].push_back(input[counter_1]);
}
std::vector<int> DaYing(DianShu);
Hashset ChaChong;
std::stack<int> Mystack;
Mystack.push(0);
ChaChong.insert(0);
DaYing[0] = 0;
int DaYingIndex = 1;
std::vector<int> WhoLongest(DianShu, -1);
WhoLongest[0] = 0;
while (!Mystack.empty()) {
int Cur = Mystack.top();
if (NodeArray[Cur].size() == 1) WhoLongest[Cur] = Mystack.size();
Mystack.pop();
for (int NextNodes : NodeArray[Cur]) {
if (ChaChong.count(NextNodes) == 0) {
Mystack.push(Cur);
Mystack.push(NextNodes);
DaYing[DaYingIndex] = NextNodes;
DaYingIndex++;
ChaChong.insert(NextNodes);
break;
}
}
}
int GetLongest = 0;
for (int counter_1 = 0;counter_1 < DianShu;counter_1++) {
GetLongest = WhoLongest[counter_1] > GetLongest ? WhoLongest[counter_1] : GetLongest;
}
int GetLongestNode = FanHuiXiaoBiao(WhoLongest, GetLongest);//具体节点号
GetLongestNode = FanHuiXiaoBiao(DaYing, GetLongestNode);
std::stack<int> fuzhu_CurLuJin;
int ChuShiIndex = GetLongestNode;
fuzhu_CurLuJin.push(ChuShiIndex);
for (int counter_1 = ChuShiIndex - 1;counter_1 >= 0;counter_1--) {
int DangQianNode = fuzhu_CurLuJin.top();//是下标
if (ISLianJie(DaYing[DangQianNode], DaYing[counter_1], NodeArray)) {
fuzhu_CurLuJin.push(counter_1);
}
}
std::vector<int> DpValue(DianShu, -1);
while (!fuzhu_CurLuJin.empty()) {
DpValue[fuzhu_CurLuJin.top()] = 0;
fuzhu_CurLuJin.pop();
}
for (int counter_1 = 0;counter_1 < DianShu;counter_1++) {
if (DpValue[counter_1] != 0) {
for (int counter_2 = counter_1 - 1;counter_2 >= 0;counter_2--) {
if (ISLianJie(DaYing[counter_2], DaYing[counter_1], NodeArray)) {
DpValue[counter_1] = DpValue[counter_2] + 1;
break;
}
}
}
}
int TongJi = 0;
for (int counter_1 = 0;counter_1 < DianShu;counter_1++) {
if (DpValue[counter_1] == 0) TongJi++;
}
MP -= (TongJi - 1);
if (MP <= 1 && MP >= 0) {
std::cout << TongJi;
return 0;
}
if (MP < 0) {
std::cout << MP + TongJi;
return 0;
}
std::stack<int> HelpMeChange;
while (MP > 1) {
int Cur_Change = GetMaxIndex_XianZhi(DpValue, MP);
if (Cur_Change == 0) break;
if (DpValue[Cur_Change] == 0) break;
MP -= DpValue[Cur_Change] * 2;
DpValue[Cur_Change] = 0;
HelpMeChange.push(DaYing[Cur_Change]);
for (int counter_1 = Cur_Change - 1;counter_1 >= 0;counter_1--) {
if (DpValue[counter_1] != 0 && ISLianJie(DaYing[counter_1], HelpMeChange.top(), NodeArray)) {
DpValue[counter_1] = 0;
HelpMeChange.pop();
HelpMeChange.push(DaYing[counter_1]);
}
}
HelpMeChange.pop();
for (int counter_1 = 0;counter_1 < DianShu;counter_1++) {
if (DpValue[counter_1] != 0) {
for (int counter_2 = counter_1 - 1;counter_2 >= 0;counter_2--) {
if (ISLianJie(DaYing[counter_2], DaYing[counter_1], NodeArray)) {
DpValue[counter_1] = DpValue[counter_2] + 1;
break;
}
}
}
}
}
int counterZeros = 0;
for (int counter_1 = 0;counter_1 < DianShu;counter_1++) {
if (DpValue[counter_1] == 0) counterZeros++;
}
std::cout << counterZeros;
return 0;
}
发表于 2021-03-21 09:59:26
回复(1)
问题信息
通过挑战的用户
-
2022-09-17 10:29:52 -
2022-09-14 17:05:53
-
2022-09-06 13:05:30
-
2022-09-01 21:56:13
-
2022-08-27 13:35:34
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
