2037. 使每位学生都有座位的最少移动次数

简介: 一个房间里有 n 个座位和 n 名学生,房间用一个数轴表示。给你一个长度为 n 的数组 seats ,其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ,其中 students[j] 是第 j 位学生的位置。

一个房间里有 n 个座位和 n 名学生,房间用一个数轴表示。给你一个长度为 n 的数组 seats ,其中 seats[i] 是第 i 个座位的位置。同时给你一个长度为 n 的数组 students ,其中 students[j] 是第 j 位学生的位置。

你可以执行以下操作任意次:

增加或者减少第 i 位学生的位置,每次变化量为 1 (也就是将第 i 位学生从位置 x 移动到 x + 1 或者 x - 1)
请你返回使所有学生都有座位坐的 最少移动次数 ,并确保没有两位学生的座位相同。

请注意,初始时有可能有多个座位或者多位学生在 同一 位置。

 

示例 1:

输入:seats = [3,1,5], students = [2,7,4]

输出:4

解释:学生移动方式如下:

  • 第一位学生从位置 2 移动到位置 1 ,移动 1 次。
  • 第二位学生从位置 7 移动到位置 5 ,移动 2 次。
  • 第三位学生从位置 4 移动到位置 3 ,移动 1 次。

总共 1 + 2 + 1 = 4 次移动。

示例 2:

输入:seats = [4,1,5,9], students = [1,3,2,6]

输出:7

解释:学生移动方式如下:

  • 第一位学生不移动。
  • 第二位学生从位置 3 移动到位置 4 ,移动 1 次。
  • 第三位学生从位置 2 移动到位置 5 ,移动 3 次。
  • 第四位学生从位置 6 移动到位置 9 ,移动 3 次。

总共 0 + 1 + 3 + 3 = 7 次移动。

示例 3:

输入:seats = [2,2,6,6], students = [1,3,2,6]

输出:4

解释:学生移动方式如下:

  • 第一位学生从位置 1 移动到位置 2 ,移动 1 次。
  • 第二位学生从位置 3 移动到位置 6 ,移动 3 次。
  • 第三位学生不移动。
  • 第四位学生不移动。

总共 1 + 3 + 0 + 0 = 4 次移动。
 

提示:
首先来分析原题目,
不管容器中的数据是否有序,一个数据要去找和他接近的数据,才能使他们的差和最小,最小的总是要去找最小的数据,
所以不要盲目去做题,
先来排序,会使问题变得非常简单。
排好之后,我们可以发现,seats,students容器里面的数据从小到大,一一对应了
那么,
我们就可以直接对应相减,既可以得到最小值。
n == seats.length == students.length
1 <= n <= 100
1 <= seats[i], students[j] <= 100
通过次数23,206提交次数27,239

来源:力扣(LeetCode)

class Solution {
public:

int minMovesToSeat(vector<int>& seats, vector<int>& students) {
   
 sort(seats.begin(), seats.end());
    sort(students.begin(), students.end());
    int res = 0;
    for (int i = 0; i < seats.size(); i++) {
        res += abs(seats[i] - students[i]);
    }
    return res;

}

};

目录
相关文章
|
17天前
|
算法 测试技术 C#
【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
【最大值线段树】【二分查找】2286. 以组为单位订音乐会的门票
|
9月前
循环结构-慈善募捐——在全院10000学生中,征集慈善募捐,当总数达到10万元时就结束,统计此时捐款的人数,以及平均每人捐款的数目。
循环结构-慈善募捐——在全院10000学生中,征集慈善募捐,当总数达到10万元时就结束,统计此时捐款的人数,以及平均每人捐款的数目。
179 0
|
9月前
L2-009 抢红包 (25 分)(结构体排序)
L2-009 抢红包 (25 分)(结构体排序)
46 0
L2-009 抢红包 (25 分)(结构体排序)
|
10月前
|
C语言
LeetCode刷题集(二)(LeetCode 2037使每位学生都有座位的最少移动次数)
LeetCode刷题集(二)(LeetCode 2037使每位学生都有座位的最少移动次数)
44 0
|
11月前
|
算法
红包随机算法,给定一定的金额,一定的人数,保证每个人都能随机获得一定的金额。...
红包随机算法,给定一定的金额,一定的人数,保证每个人都能随机获得一定的金额。...
130 0
【每日一题Day73】LC2037使每位学生都有座位的最少移动次数 | 排序+贪心
思路:要使总移动次数最少,那么要将每个学生移动至离其最近的座位,因此将座位和学生的位置进行升序排序,每个学生需要的移动次数即为对应位置相减,累加返回最终结果
70 0
刷爆力扣之至少是其它数字两倍的最大数
刷爆力扣之至少是其它数字两倍的最大数
|
人工智能 BI
L3-001 凑零钱 (30 分)
L3-001 凑零钱 (30 分)
114 0
h0131. 钞票 (15 分)
h0131. 钞票 (15 分)
79 0