#蔚来笔试# 蔚来笔试正式批 8.6  求助怎么做 自己太菜了 有没有好心人帮忙解答一下
有n棵苹果树,这些苹果树上一共有m个苹果,每个苹果有两个参数(pos;, hi),分别代表苹果所在的苹果树编号和高度。
对于每一棵苹果树,牛牛都可以选择一个长度为k的区间,得到高度在这个区间的所有苹果。
牛牛要怎么操作才能得到最多的苹果,输出最多的苹果个数。

输入描述:第一行为三个整数n,m,k,分别代表苹果树个数,苹果个数,可以选择区间的长度。(0 < n ≤1000,0 < m <100000,1 接下来有m 行,每行两个整数(pos;,hi),代表每个苹果的位置参数。(1≤pos;≤ n,1 
输入
2 5 3
1 12 
1 4 
2 9
2 7
2 44
输出:3
第1棵树选择区间[2,4],得到1个苹果
第棵树选择区间[7,9],得到2个苹果
所以得到最多的苹果个数为3个

全部评论
滑动窗口模拟一下不就可以啦
点赞 回复
分享
发布于 2022-08-07 01:12
int solution(vector<vector<int>>& apples, int m, int n, int k){ vector<vector<int>> tree_heights(n); for (int i = 0; i < m; i++) { tree_heights[apples[i][0]-1].push_back(apples[i][1]); } int res = 0; for (int i = 0; i < n; i++) { sort(tree_heights[i].begin(), tree_heights[i].end()); int max_cnt = INT_MIN; for (int j = 0; j < tree_heights[i].size(); j++) { int upper = tree_heights[i][j] + k; int cnt = 1, start = j + 1; while (start < tree_heights[i].size() && tree_heights[i][start] <= upper) { cnt++; start++; } max_cnt = max(max_cnt, cnt); } res += max_cnt; } return res; }
点赞 回复
分享
发布于 2022-08-09 17:16
滴滴
校招火热招聘中
官网直投
能用java吗
点赞 回复
分享
发布于 2022-08-15 17:37

相关推荐

点赞 评论 收藏
转发
3 6 评论
分享
牛客网
牛客企业服务