首页 > 试题广场 >

换位

[编程题]换位
  • 热度指数：185 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给出两个数列，求使第一个数列严格降序，第二个数列严格升序的最少交换次数

若无法交换成严格有序，返回“-1”

示例1

输入

[5,4,3,2,1],[1,2,3,4,5]

输出

0

说明

显然，这个排列已经满足要求，不需要交换。
示例2

输入

[1,2,3,4,5],[5,4,3,2,1]

输出

4
示例3

输入

[3,2,1],[1,3,3]

输出

-1

说明

别忘了如果怎么交换都不能满足要求，你应该返回 -1。

备注:
注意，本题中为严格大于小于关系，即 [1,2,3] 可以看作由升序，但是 [1,3,3] 不行。

数据范围：
- 对于 20% 的数据，
- 对于 60% 的数据，
- 对于 100% 的数据，

对于 100% 的数据，两个数组的大小均恰好为 ，且两个数组  的元素均满足 。
算法知识视频讲解
开通博客
头像 炊烟晚霞
发表于 2020-08-15 22:43:51
题目 牛牛是一位优秀的程序员。最近，牛牛在的公司要办年会了。牛牛所在的组要表演一个比较有意思的大合唱，程序员们站在第一排，产品经理们站在第二排。为了让年会节目更有吸引力，牛牛在设计站位上下了功夫：从左往右，程序员们由高到矮进行站位，而产品经理们则按由矮到高进行站位，两个队列的上下场方向也不一样，这样 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 摸鱼学大师
发表于 2021-09-29 20:14:15
题目的主要信息： 给出两个等长的数列，求使第一个数列严格降序，第二个数列严格升序的最少交换次数 交换是指第一个数组中相对应的位置交换到第二个数组相对应位置 若无法交换成严格有序，返回“-1” 方法一：动态规划 具体做法：我们用两个动态规划数组来描述，其中dp1[i]表示第i个元素不需要调整即可满 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 xqxls
发表于 2021-09-18 16:06:30
题意整理 给定两个同样大小的数列，现在要将第一个变为严格降序，第二个变为严格升序。 可以交换两个数列同一列的元素，问最少交换多少次。 如果无法交换成严格有序，返回-1。 方法一（动态规划） 1.解题思路 状态定义：表示当前无交换的最少交换次数，表示当前有交换的最少交换次数。 状态初始化：当只有 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

动态规划
难度：
0条回答 691浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号