LeetCode·每日一题·2037.使每位学生都有座位的最少移动次数·贪心
LeetCode 移动 每日 学生 贪心 次数 最少
2023-09-27 14:26:29 时间
作者:小迅
链接:https://leetcode.cn/problems/minimum-number-of-moves-to-seat-everyone/solutions/2038972/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-0dtp1/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
题意 -> 移动最少的步数,使得座位下标相同
对于最值问题我们普遍采用贪心或者动态规划,对于本题我们使用贪心比较方便,对于任意一个位置,我们要使得移动次数最少,肯定就需要将学生移动到就近的位置,这样才能使得每次移动都最小,从而整体最少
我们先对两个数组进行排序,使得座位和学生的按顺序排列,这样座位和学生就满足就近原则,直接移动即可
代码
int cmp(const void *a, const void *b) //排序子函数
{
return *(int *)a - *(int *)b;
}
int minMovesToSeat(int* seats, int seatsSize, int* students, int studentsSize){
qsort(seats, seatsSize, sizeof(int), cmp);
qsort(students, studentsSize, sizeof(int), cmp);//排序
int count = 0;
for (int i = 0; i < seatsSize; ++i) {//累加移动步数
count += abs(seats[i] - students[i]);
}
return count;
}
作者:小迅
链接:https://leetcode.cn/problems/minimum-number-of-moves-to-seat-everyone/solutions/2038972/tan-xin-zhu-shi-chao-ji-xiang-xi-by-xun-0dtp1/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
相关文章
- 【LeetCode】电话号码的字母组合 [M](深度优先遍历)
- 【LeetCode】最大子数组和 [M](动态规划)
- LeetCode_回溯_中等_93.复原 IP 地址
- LeetCode_前缀和_中等_1769.移动所有球到每个盒子所需的最小操作数
- LeetCode_哈希表_排序_中等_451.根据字符出现频率排序
- LeetCode_博弈_中等_877.石子游戏
- LeetCode_双指针_简单_283.移动零
- LeetCode_Boyer-Moore 投票算法_简单_169.多数元素
- LeetCode刷题(14)【简单】加一(C++)
- LeetCode·每日一题·856.括号的分数·栈模拟
- LeetCode------移动零(5)【数组】
- [leetcode] Reverse Words in a String [1]
- LeetCode-861. 翻转矩阵后的得分(Java实现)
- [LeetCode] 244. Shortest Word Distance II 最短单词距离 II
- leetcode 1049 最后一块石头的重量
- leetcode 45跳跃游戏II