2023校招美团笔试

这两天状态不是很好，美团笔试的题比较常规，五个编程，没有选择填空，做的一般，A了两道多，脑子感觉因为天天熬夜有点迟钝，最后几个题直接摆烂了。

第一题：送外卖

这道题当时思路出了点问题，这道题我思路是从0到n*T，分段讨论，比如现在是8个用户，他们的截至时间分别是6 10 4 5 40 42 11 15外卖员送餐时间是5
可以分成n段，在这是8段
0 5 10 15 20 25 30 35 40
应该是比如骑手送了第一次，那应该截止时间小于骑手的都要用魔法，当时想成了小于在这个区间里的骑手都能送到，只有冲突了才送不到，所以最后用例只过了20%。。。。
题目大意;有n个点餐用户，只有一个外卖员，每个点餐用户都有一个截至日期，必须在这个时间前送到，而外卖员送每一次的时间是固定的T,外卖员不能同时送两份外卖，如果出现冲突，外卖员可以使用魔法。问外卖员最少使用几次魔法。

这是外卖员不用魔法，在n*t的时间内送n次
我们要做的就是在每个区间寻找是否有冲突的用户

第一次：5，如果外卖员送了第一次，小于5的用户，那这个用户肯定是送不到了，得用魔法，外卖员送了第一次，去掉>=5 的截止时间最短的用户的需求，4要用魔法，5可以送到去掉，下次从6开始判断
第二次：10，6送不到用秘法，10可以送到，下次从11开始判断
第三次：15，11用魔法，15送到，下次从40开始判断
第四次：20，40可以送到
第五次：25，42可以送到

#include 
#include 
#include 
using namespace std;
// 6 5 5 6 7 8 9 10
int main(){
  int n,t;
  cin >> n >> t;
  vector<int>vec;
  for(int i = 0; i < n; i++){
  	int num;
	cin >> num;
    vec.push_back(num);
  }
  sort(vec.begin(),vec.end());
  int res = 0;
  int shortdex = 0;
  for(int curtime = t; curtime <= n * t; curtime += t){
  	while(shortdex < n && vec[shortdex] < curtime){
  		res++;
  		shortdex++;
	}
	shortdex++;
  }
  cout << res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第二题：打扫房间

这道题A出来了，本以为是广度优先搜索，后面发现好像不是
题目大意：一个房间，刚开始扫地机器人在0，0也就是左上角处，并且这个地是默认已经打扫的，接着给一串字符，WASD四种字符组成，分别代表上左下右四种操作，默认这个操作都是合法的，也就是不会有超出房间范围的操作，问：
字符串操作结束后，是否打扫干净/
1.打扫干净的话：问第几个指令的时候打扫干净的
2.如果么有打扫干净：问还有几个房间没有打扫干净

这个题比较简单，关键是做好记录，首先创建一个nm的二维数组，0，0已经打扫干净，我们需要打扫nm-1个格子，遍历字符串，对当前位置的X,Y坐标进行响应的加减变换，如果变换后的位置是0,就把它3变为1，且将未打扫格子数目减一，如果遍历过程中，未打扫格子数为0了，就退出并返回当前i值，如果遍历结束未打扫格子数仍然大于0，就返回剩余格子数。
注意输出格式，区分大小写和换行哦~~~~~~~~

#include 
#include 
using namespace std;

int main(){
  int n,m,k;
  cin >> n >> m >> k;
  string s;
  cin >> s;
  vector<vector<int>> visited(m,vector<int>(m,0));
  visited[0][0] = 1;
  int x = 0;
  int y = 0;
  int memory = n*m-1;
  for(int i = 0; i < k; i++){
    if(s[i] == 'W'){
      y--;
    }else if(s[i] == 'A'){
      x--;
    }else if(s[i] == 'S'){
      y++;
    }else if(s[i] == 'D'){
      x++;
    }
    if(visited[x][y] == 0){
      visited[x][y] = 1;
      memory--;
    }
    if(memory==0){
      cout << "Yes" << endl << i;
      return 0;
    }
  }
  cout << "No" << endl << memory;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

第三题：翻扑克

正向翻有点像约瑟夫环，逆向有点想不明白
题目大意，有一副点数从1到n的牌，对这副牌先取牌堆顶一张放到牌堆底，再取牌堆顶一张放到牌堆底，然后翻开牌堆顶的那张，重复下去直到最后一张被翻开。

约瑟夫环问题
https://leetcode.cn/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
这个题就是一个逆向的约瑟夫环问题，其中m等于2

这里注意下标和求的值不一样，差一位，所以求下标应该对当前最大坐标取余。

int cir(int dex)
{
	return nums[i]+2)%i+1;
}

1
2
3
4
5

第四题：三元组的问题

这个三个for循环暴力做的过了80%好像
题目是：一个数组下标 i < j < k的三个数，现在有个关系式，a[i] - a[j] = 2a[j] + a[k]；
求出所有满足的三元组

这个应该像百钱百鸡问题要先变换式子，不能无脑暴力

第五题：求到叶子节点最大路径和

题目输入是一个数组形式，应该是二叉完全树，所以直接广搜求出所有结果取最大即可
https://leetcode.cn/problems/path-sum/solution/lu-jing-zong-he-by-leetcode-solution/