2022-08-06 19:52
不愿透露姓名的神秘牛友
#蔚来笔试# 蔚来笔试正式批 8.6 求助怎么做 自己太菜了 有没有好心人帮忙解答一下
有n棵苹果树，这些苹果树上一共有m个苹果，每个苹果有两个参数(pos;, hi),分别代表苹果所在的苹果树编号和高度。
对于每一棵苹果树，牛牛都可以选择一个长度为k的区间，得到高度在这个区间的所有苹果。
牛牛要怎么操作才能得到最多的苹果，输出最多的苹果个数。
输入描述：第一行为三个整数n,m，k，分别代表苹果树个数，苹果个数，可以选择区间的长度。(0 < n ≤1000,0 < m <100000,1
输入
2 5 3
1 12
1 4
2 9
2 7
2 44
输出：3
第1棵树选择区间[2，4]，得到1个苹果
第棵树选择区间[7，9]，得到2个苹果
所以得到最多的苹果个数为3个
有n棵苹果树，这些苹果树上一共有m个苹果，每个苹果有两个参数(pos;, hi),分别代表苹果所在的苹果树编号和高度。
对于每一棵苹果树，牛牛都可以选择一个长度为k的区间，得到高度在这个区间的所有苹果。
牛牛要怎么操作才能得到最多的苹果，输出最多的苹果个数。
输入描述：第一行为三个整数n,m，k，分别代表苹果树个数，苹果个数，可以选择区间的长度。(0 < n ≤1000,0 < m <100000,1
输入
2 5 3
1 12
1 4
2 9
2 7
2 44
输出：3
第1棵树选择区间[2，4]，得到1个苹果
第棵树选择区间[7，9]，得到2个苹果
所以得到最多的苹果个数为3个
全部评论
pika_pika
门头沟学院 C++
滑动窗口模拟一下不就可以啦
再想想吧
上海交通大学 C++
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;
}
强大的奇亚籽最喜欢春天
深圳大学 Java
能用java吗
相关推荐
投递宁波灵均投资北京朝阳分部等公司10个岗位 >