罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法

这篇具有很好参考价值的文章主要介绍了罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【题目来源】
http://oj.ecustacm.cn/problem.php?id=1812
http://oj.ecustacm.cn/viewnews.php?id=1023

【题目描述】
给定一个长度为 n 的排列 a,需要将这个排列变成 b。
每次可以选择一个数字往左移若干个位置。
请求出
最小需要移动的元素个数

【输入格式】
第一行为正整数 n,1≤n≤100000。
第二行为 n 个整数,表示排列 a。
第三行为 n 个整数,表示排列 b。

【输出格式】
输出一个数字表示答案,即最小需要移动的元素个数。

【输入样例】
5
5 1 3 2 4
4 5 2 1 3

【输出样例】
2

【算法分析】
** 将原序列 a 重排为序列 b,则原序列 a 中各元素在序列 b 中的位置 p[] 可通过以下代码获得:

tp[b[i]]=i, p[i]=tp[a[i]]
** 分析位置序列 p[] 中每个数,如果当前的数比左边的数小就不断左移,否则不用移动。这是贪心算法的思路。
例如,针对样例中给出的原始序列 a[]=[5 1 3 2 4] 中的各元素,利用“
tp[b[i]]=i, p[i]=tp[a[i]]”,可得出它们在重排序列 b[]=[4 5 2 1 3] 中的位置序列为 p[]=[2 4 5 3 1]。显然,通过观察位序的相对位置,可知需要移动两个数字。

【算法代码】

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int a[N],b[N];
int p[N]; //p[x]:subscript of number x in the b array
int tp[N];

int main() {
    int n;
    cin>>n;
    for(int i=1; i<=n; i++) cin>>a[i];
    for(int i=1; i<=n; i++) {
        cin>>b[i];
        tp[b[i]]=i;
    }
    for(int i=1; i<=n; i++) p[i]=tp[a[i]];

    int ans=0;
    int t=0;
    for(int i=1; i<=n; i++) {
        if(t>p[i]) ans++;
        t=max(t,p[i]);
    }
    cout<<ans<<endl;
    
    return 0;
}


/*
in:
5
5 1 3 2 4
4 5 2 1 3

out:
2
*/




【参考文献】
https://blog.csdn.net/weixin_43914593/article/details/131741061





 文章来源地址https://www.toymoban.com/news/detail-660776.html

到了这里,关于罗勇军 → 《算法竞赛·快冲300题》每日一题:“排列变换” ← 贪心算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《算法竞赛·快冲300题》每日一题:“彩虹数”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 彩虹数 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1840 【题目描述】 彩虹数:一个无

    2024年02月09日
    浏览(48)
  • 《算法竞赛·快冲300题》每日一题:“糖果配对”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 糖果配对 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1735 【题目描述】 现在有N个小朋

    2024年02月12日
    浏览(46)
  • 《算法竞赛·快冲300题》每日一题:“点灯游戏”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 点灯游戏 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1134 【题目描述】 有一个n*n的灯

    2024年02月08日
    浏览(48)
  • 《算法竞赛·快冲300题》每日一题:“凑二十四”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 凑二十四 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1793 【题目描述】 给你n个数字,

    2024年02月11日
    浏览(37)
  • 《算法竞赛·快冲300题》每日一题:“松鼠与栗子”

    《 算法竞赛·快冲300题 》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 “ 松鼠与栗子 ” ,链接: http://oj.ecustacm.cn/problem.php?id=1852 【题目描述】 现在有m棵栗

    2024年02月11日
    浏览(43)
  • 【C语言蓝桥杯每日一题】——排列字母

    TOC     😎博客昵称:博客小梦 😊最喜欢的座右铭:全神贯注的上吧!!! 😊作者简介:一名热爱C/C++,算法等技术、喜爱运动、热爱K歌、敢于追梦的小博主! 😘博主小留言:哈喽! 😄各位CSDN的uu们,我是你的博客好友小梦,希望我的文章可以给您带来一定的帮助,话

    2023年04月09日
    浏览(47)
  • ( 数组和矩阵) 667. 优美的排列 II ——【Leetcode每日一题】

    难度:中等 给你两个整数 n 和 k ,请你构造一个答案列表 answer ,该列表应当包含从 1 到 n 的 n 个不同正整数,并同时满足下述条件: 假设该列表是 answer = [a1, a2, a3, ... , an] ,那么列表 [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] 中应该有且仅有 k 个不同整数。 返回列表 answer

    2024年02月06日
    浏览(46)
  • (搜索) 剑指 Offer 38. 字符串的排列 ——【Leetcode每日一题】

    难度:中等 输入一个字符串,打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组,但里面 不能有重复元素 。 示例: 输入:s = “abc” 输出:[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”] 限制 : 1 = s 的长度 = 8 💡思路:回溯 可以直接 暴力穷举 ,但

    2024年02月12日
    浏览(51)
  • 算法|每日一题|H 指数|二分

    原题地址: 力扣每日一题:H 指数 给你一个整数数组 citations ,其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。 根据维基百科上 h 指数的定义:h 代表“高引用次数” ,一名科研人员的 h 指数 是指他(她)至少发表了 h 篇论文,并且每

    2024年02月08日
    浏览(42)
  • 每日一题之常见的排序算法

    排序是最常用的算法,常见的排序算法有冒泡排序、选择排序、插入排序、快速排序、希尔排序和归并排序。除此之外,还有桶排序、堆排序、基数排序和计数排序。 1、冒泡排序 冒泡排序就是把小的元素往前放或大的元素往后放,比较的是相邻的两个元素。 时间复杂度:

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包