天上掉馅饼--移动研究院2018校招笔试题

关键词：

题目：

天上掉馅饼
时间限制：C/C++语言 1000MS；其他语言 3000MS
内存限制：C/C++语言 131072KB；其他语言 655360KB
题目描述：
大家都知道“天上不会掉馅饼”这句话，但是有一天，小明在回学校的路上，天上还真掉起了馅饼。小明的人品实在有点好，这馅饼会掉在小明身边10米的范围内。馅饼掉在地上显然就不能吃了，所以小明马上拿起他的背包去接。但是，小明是个技术宅，运动方面实在不太行，每秒钟只有在移动不超过1米的范围内接住馅饼。这条小路的图所示如下：

现在，我们把问题简化一下，馅饼现在只掉在0~10这11个位置。开始时，小明站在5这个位置，因此在第一秒，他只能接到4,5,6这三个位置其中一个位置的馅饼。问小明最多能接多少个馅饼？请用Java/python/C++/C语言中的一种进行编程。
输入
测试数据多组，每组测试数据都会给出一共掉落的馅饼数N，接下里的N行给出每次馅饼掉落的坐标X和掉落的时间T。同一秒可能掉落多个馅饼。（0<N,T<100000）
输出
对于每个测试数据，输出一个整数，代表小明能够获得最多馅饼数量。

样例输入
6
5 1
4 1
6 1
7 2
7 2
8 3
样例输出
Case #1:
The max number of pies is : 4

思路：时间从0开始到没有馅饼掉落为止，遍历所有可能的移动方式，以及每种方式所获得的馅饼数，取最大值。

代码（未在考试平台上测试）：

 1 import java.util.*;
 2 
 3 public class Main{
 4     private void func(int endTime, int curTime, int mingPlace, Map<Integer, ArrayList<Integer>> timePlaceMap,
 5                      int curNum, ArrayList<Integer> numList) {
 6         if (curTime > endTime) {
 7             numList.add(curNum);
 8             return;
 9         }
10 
11         // 计算移动-1，0，+1步能获得的馅饼数目
12         int num_here = 0, num_before = 0, num_behind = 0;
13         if (timePlaceMap.containsKey(curTime+1)) {
14             ArrayList<Integer> places = timePlaceMap.get(curTime + 1);
15             System.out.println("places:" + places);
16             for (int place: places) {
17                 if (place == mingPlace) {
18                     num_here++;
19                 } else if (mingPlace > 0 && place == mingPlace - 1) {
20                     num_before++;
21                 } else if (mingPlace < 10 && place == mingPlace + 1) {
22                     num_behind++;
23                 }
24             }
25         }
26         
27         func(endTime, curTime+1, mingPlace, timePlaceMap,
28                 curNum + num_here, numList);// 位置不变
29         if (mingPlace > 0) {
30             func(endTime, curTime+1, mingPlace-1, timePlaceMap,
31                     curNum + num_before, numList);// 位置减1
32         }
33         if (mingPlace < 10) {
34             func(endTime, curTime+1, mingPlace+1, timePlaceMap,
35                     curNum + num_behind, numList);// 位置加1
36         }
37     }
38 
39     public static void main(String[] args) {
40         Main mainClass = new Main();
41         Scanner in = new Scanner(System.in);
42         while(in.hasNext()) {
43             String input = in.next();
44             int n = Integer.parseInt(input);
45             Map<Integer, ArrayList<Integer>> timePlaceMap = new HashMap<>();
46             for (int i=0; i<n; i++) {
47                 int place = Integer.parseInt(in.next());
48                 int time = Integer.parseInt(in.next());
49                 ArrayList<Integer> places = timePlaceMap.getOrDefault(time, new ArrayList<Integer>());
50                 places.add(place);
51                 timePlaceMap.put(time, places);
52             }
53             int endTime = Collections.max(timePlaceMap.keySet());
54             ArrayList<Integer> numList = new ArrayList<>();
55             mainClass.func(endTime, 0, 5, timePlaceMap, 0, numList);
56             int maxNum = Collections.max(numList);
57             System.out.println(" The max number of pies is : " + maxNum);
58         }
59         in.close();
60     }
61 }

清北学堂模拟赛d7t3天上掉馅饼

题目描述小G进入了一个神奇的世界，在这个世界，天上会掉下一些馅饼。今天，天上会随机掉下k个馅饼。每次天上掉下馅饼，小G可以选择吃或者不吃（必须在下一个馅饼掉下来之前作出选择，并且现在决定不吃的话以后也不能... 查看详情

微软2017校招笔试题2composition

题目AlicewritesanEnglishcompositionwithalengthofNcharacters.However,herteacherrequiresthatMillegalpairsofcharacterscannotbeadjacent,andif‘ab‘cannotbeadjacent,‘ba‘cannotbeadjacenteither.Inordertomeetther 查看详情

微软2017校招笔试题3registrationday

题目It‘sHUniversity‘sRegistrationDayfornewstudents.ThereareMofficesinHUniversity,numberedfrom1toM.Studentsneedtovisitsomeoftheminacertainordertofinishtheirregistrationprocedures.Theofficesareindifferent 查看详情

免费馅饼

题目描述都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所... 查看详情

小米2017校招笔试题

只过了20%...我日树的高度 时间限制：C/C++语言1000MS；其他语言3000MS 内存限制：C/C++语言65536KB；其他语言589824KB 题目描述： 现在有一棵合法的二叉树，树的节点都是用数字表示， 现在给定这棵树上所有的父子关系，求这棵树的高... 查看详情

免费馅饼

...bsp;ms | 内存限制：65535 KB难度：3描写叙述都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上。忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了。这馅饼别处都不掉，就掉落在他身旁的10米范围内... 查看详情

奇虎3602017校招笔试题

最强大脑时间限制：C/C++语言1000MS；其他语言3000MS内存限制：C/C++语言65536KB；其他语言589824KB题目描述：小B乘火车和朋友们一起在N市到M市之间旅行。她在路途中时睡时醒。当她醒来观看窗外的风景时，注意到每个火车站都有一... 查看详情

lgyx2017校招笔试题

前言今天通知过了笔试，但总感觉有些笔试没来得及做的题不解决不舒服斯基。题目 大意就是，给你个形如a,b,c,ab,bb,cb,ac,bc,cc,aab,bab,cab,abb,bbb,cbb,acb,bcb,ccb......按某种规律排列的无限长的字符串数组，要求：1）给定一个位置，... 查看详情

校招笔试题大杂烩

1、某表达式的前缀形式为"+-*^ABCD/E/F+GH",运算符优先级为^>*/>-+,它的中缀形式为(C)A  A^B*C-D+E/F/G+H  B A^B*(C-D)+(E/F)/G+H  C  A^B*C-D+E/(F/(G+H))  D A^B*(C-D)+ 查看详情

免费馅饼

Description都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以... 查看详情

快手2019校招笔试题(代码片段)

目的：分别从前面和后面开始找划分点，使得前面的数字之和=后面的数字之和目标表述：sum(前面m个数)=sum(后面n个数）s.t.m+n<=N（总个数）变形：sum[i]表示前i个数之和，sum2[i]表示后i... 查看详情

nyoj613免费馅饼

...1000 ms | 内存限制：65535 KB难度：3描述都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内... 查看详情

兆易创新9月校招笔试题_ic设计/验证

       还有器件岗位的笔试题：1、CMOS中哪些制造步骤中用到了离子注入，需要注意哪些？2、有哪些薄膜制备方法？各有什么优缺点？3、COMS的制作步骤，简要叙述。4、载流子的输运方式有哪些，简要叙... 查看详情

网易2017年校招笔试题最大的奇约数

题目：定义函数f(x)为x的最大奇数约数，x为正整数，例如f(44)=11.现在给出一个N,需要求出f(1)+f(2)+f(3)+...+f(N)例如：N=7f(1)+f(2)+f(3)+f(4)+f(5)+f(6)+f(7)=1+1+3+1+5+7=21. 分析：奇数的最大约数是自身，偶数的最大约数是是除去所有偶因子之... 查看详情

hdu-1176免费馅饼(dp)

...：http://acm.hdu.edu.cn/showproblem.php?pid=1176ProblemDescription都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。... 查看详情

网易2019校招笔试题-瞌睡(代码片段)

分析：由于小易清醒的时间是连续的，所以整个搜索空间为O(n)，根本不需要贪心或者动态规划就能搞定。小易这堂课获得的兴趣值分为两部分：本来就清醒时获得的兴趣值，被叫醒的k分钟获得的兴趣值。因为... 查看详情

hdoj1176免费馅饼(代码片段)

免费馅饼　　都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了... 查看详情

hdu-1176免费馅饼(代码片段)

题目：都说天上不会掉馅饼，但有一天gameboy正走在回家的小径上，忽然天上掉下大把大把的馅饼。说来gameboy的人品实在是太好了，这馅饼别处都不掉，就掉落在他身旁的10米范围内。馅饼如果掉在了地上当然就不能吃了，所以ga... 查看详情