备战蓝桥杯---多路归并与归并排序刷题

话不多说,直接看题

1.

我们考虑一行一行合并,一共m次,我们合并两个并取前n小,那么我们怎么取?

我们采用分组的思想:

我们选第一列的min,然后把后面那个再纳入考虑,用优先队列实现即可。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=2010;
typedef pair<int,int> pii;
int m,n;
int a[N],b[N],c[N];
void merge(){
    priority_queue<pii,vector<pii>,greater<pii> >heap;
    for(int i=0;i<n;i++) heap.push({a[0]+b[i],0});
    for(int i=0;i<n;i++){
        auto t=heap.top();
        heap.pop();
        int s=t.first,p=t.second;
        c[i]=s;
        heap.push({s-a[p]+a[p+1],p+1});
    }
    for(int i=0;i<n;i++) a[i]=c[i];
}
int main(){
    int t;
    cin>>t;
    while(t--){
        cin>>m>>n;
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a,a+n);
        for(int i=0;i<m-1;i++){
            for(int j=0;j<n;j++) scanf("%d",&b[j]);
            merge();
        }
        for(int i=0;i<n;i++) printf("%d ",a[i]);
        cout<<endl;
    }
}

2.

首先我们把1放入丑数,令i,j,k指向它(代表2,3,5),然后我们选min的成1,变成2,此时i指向2,然后我们再从3,5,2*2中选min的3,此时j指向2,依次类推,每用一次就向后移一下。下面是AC代码:

class Solution {
public:
    int getUglyNumber(int n) {
       vector<int> q(1,1);
       int i=0,j=0,k=0;
       while(--n){
           int t=min(q[i]*2,min(q[j]*3,q[k]*5));
           q.push_back(t);
           if(q[i]*2==t) i++;//这里若有两个都=x,两个指针都要移
           if(q[j]*3==t) j++;
           if(q[k]*5==t) k++;
       }
       return q.back();
    }
};

3.

首先,两个数都从大到小排这样对于就是min,我们先考虑A1234B3241(离散化后)我们假设A不动,那么答案就是B的逆序对的数量,假如A可以动?因为此时两个逆序对之差就是B的逆序对,而假如要凑出答案,那么他们的逆序对一定为0,而每一次移动去1个逆序对,所以答案还是B的逆序对,跟进一步,假如A乱序?我们不妨做一个映射,把A的每一个数都映射为1234.。。然后换一下B即可。至于逆序对用树状数组即可,下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100010,mod=99999997;
int n;
int a[N],b[N],c[N],p[N],tr[N];
long long sum[100010];
void work(int a[]){//离散化
    for(int i=1;i<=n;i++) p[i]=i;
    sort(p+1,p+n+1,[&](int x,int y){
        return a[x]<a[y];
    });
    for(int i=1;i<=n;i++) a[p[i]]=i;
}
int lowbit(int x){
    return x&(-x);
}
void add(int x,int v){
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=v;
}
int query(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    work(a),work(b);
    for(int i=1;i<=n;i++){
        c[a[i]]=i;
    }
    for(int i=1;i<=n;i++){
        b[i]=c[b[i]];
    }
    for(int i=1;i<=n;i++){
        sum[i]=query(n)-query(b[i]);
        add(b[i],1);
    }
    memset(tr,0,sizeof(tr));
    for(int i=n;i>=1;i--){
        sum[i]=(sum[i]+query(b[i]-1))%mod;
        add(b[i],1);
    }
    
    long long ans=0;
    for(int i=1;i<=n;i++) ans=(ans+sum[i]);
    cout<<ans/2%mod;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/518857.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

今年考研是太卷了还是太水了,为什么分数线都高的离谱?

25考研的备考形势&#xff0c;势必跟以前不一样了&#xff01; 有些人问&#xff0c;分数线那么高&#xff0c;是不是题目太水了&#xff1f; 问的人肯定不是24考生。 24的题&#xff0c;也就政治正常一点。 其它的&#xff0c;英语难上热搜&#xff0c;数学难度空前&#x…

04---webpack编写可维护的构建配置

01 构建配置抽离成npm包&#xff1b; 意义&#xff1a;通用性&#xff1a; 业务开发者无需关注构建配置 统一团队构建脚本可维护性&#xff1a;构建配置合理的拆分 质量&#xff1a;冒烟测试 单元测试 持续集成构建配置管理的可选方案&#xff1a;1 通过多个配置文件管理不同…

一、OpenCV(C#版本)环境搭建

一、Visual Studio 创建新项目 二、选择Windows窗体应用&#xff08;.NET Framework&#xff09; 直接搜索模板&#xff1a;Windows窗体应用(.NET Framework) 记得是C#哈&#xff0c;别整成VB(Visual Basic)了 PS&#xff1a;若搜索搜不到&#xff0c;直接点击安装多个工具和…

【OJ】动规练习七之【模板】01背包

个人主页 &#xff1a; zxctscl 如有转载请先通知 DP41 【模板】01背包 1. DP41 【模板】01背包2. 分析3. 代码4. 优化5. 优化后代码 1. DP41 【模板】01背包 2. 分析 一、题目解析&#xff1a; 来看一下例1&#xff0c;3代表有三个物品&#xff0c;5代表能够容纳的体积。第一…

VGA 多分辨率

REVIEW VGA 时序与实现-CSDN博客 对于不同分辨率&#xff0c;每次使用都去查表比较麻烦&#xff1b; 学习条件编译的使用&#xff0c;减轻后续调用的麻烦。 1. 条件编译格式 条件编译是当设计中满足某个条件时&#xff0c;将该条件下的一段代码编译进设计中。 因此&#xff0…

C++ 类和对象(初篇)

类的引入 C语言中&#xff0c;结构体中只能定义变量&#xff0c;在C中&#xff0c;结构体内不仅可以定义变量&#xff0c;也可以定义函数。 而为了区分C和C我们将结构体重新命名成class去定义 类的定义 标准格式&#xff1a; class className {// 类体&#xff1a;由成员函…

AI绘图:Stable Diffusion ComfyUI局部重绘与智能扩图全面教程

前言 在数字艺术创作中&#xff0c;局部重绘和智能扩图是两个非常重要的功能。局部重绘允许我们在保留原有图像的基础上&#xff0c;对特定区域进行修改或创新。而智能扩图则能够帮助我们在图像的边缘添加新的元素&#xff0c;从而扩展图像的内容。本文将详细介绍如何在Stable…

深度学习pytorch好用网站分享

深度学习在线实验室Featurizehttps://featurize.cn/而且这个网站里面还有一些学习教程 免费好用 如何使用 PyTorch 进行图像分类https://featurize.cn/notebooks/5a36fa40-490e-4664-bf98-aa5ad7b2fc2f

jforgame-doctor快速入门

背景 游戏热更新,是指在不重启服务器/客户端app的情况下,对游戏内容进行修改或者对代码bug进行修复。 对于一个上线产品项目来说,热更新为维持项目的稳定健康提供了坚强的保障。小到策划数据的修改,代码bug的修改,大到动态扩展游戏业务功能。试想一下,没有热更新机制,…

基于SSM的邮票鉴赏系统(有报告)。Javaee项目。ssm项目。

演示视频&#xff1a; 基于SSM的邮票鉴赏系统&#xff08;有报告&#xff09;。Javaee项目。ssm项目。 项目介绍&#xff1a; 采用M&#xff08;model&#xff09;V&#xff08;view&#xff09;C&#xff08;controller&#xff09;三层体系结构&#xff0c;通过Spring Spri…

电脑硬盘分区表的两种格式:MBR 和 GPT

电脑硬盘分区表的两种格式&#xff1a;MBR 和 GPT 段子手168 2024-4-5 电脑硬盘分区表有两种格式&#xff1a;MBR 和 GPT&#xff1a; 一、MBR 分区表 1.MBR 是主引导记录 (Master Boot Record) 的英文缩写 在传统&#xff08;Legacy&#xff09;硬盘分区模式中&#xff0c…

1970-2021年全国区县级碳排放数据8

1970-2021年全国区县级碳排放数据 1、时间&#xff1a;1970-2021年 2、指标&#xff1a;2877个区县 3、来源&#xff1a;EDGAR 4、指标&#xff1a;二氧化碳排放量 5、样本量&#xff1a;14W 6、指标解释&#xff1a; 二氧化碳排放是一个生态环境专业术语&#xff0c;主…

项目经理必须知道的三大财务报表相关知识

清晖有个不错的讲项目经理应该知道的三大财务报表相关知识&#xff0c;地址&#xff1a;项目经理必备的财务知识_哔哩哔哩_bilibili

深度学习的数学基础--Homework2

学习资料&#xff1a;https://www.bilibili.com/video/BV1mg4y187qv/?spm_id_from333.788.recommend_more_video.1&vd_sourced6b1de7f052664abab680fc242ef9bc1 神经网络的特点&#xff1a;它不是一个解析模型&#xff0c;它的储存在一堆参数里面&#xff08;确定一个超平…

File(一),IO流,递归详解

File类 介绍 java.io.File类是Java语言提供了用来描述文件和目录(文件夹)的 构造 方法 注意&#xff1a; 构造方法中通常用的是第一个方法文件和目录可以通过File封装成对象File封装的对象仅仅是一个路径名&#xff0c;它是可以存在的&#xff0c;也可以不存在 绝对路径…

详解protected访问限定符

1.同一个包中的同一类 package demo1;public class Test1 {protected int a 10;protected void b() {System.out.println("这是protected修饰的成员方法");}public static void main(String[] args) {Test1 test new Test1();System.out.println(test.a);test.b()…

Vue学习笔记-S1

1 什么是Vue Vue是一款用于构建用户界面的渐进式JavaScripte框架&#xff0c;可基于数据渲染用户页面. 1.1 Vue的知识架构 Vue核心包&#xff1a;声明式渲染、组件系统Vue构建&#xff1a;客户端路由、状态管理、构建工具局部使用Vue&#xff1a;快速入门、常用指令、生命周…

4.5日学习打卡----学习Apache HttpClient 5

4.5日学习打卡 目录&#xff1a; 4.5日学习打卡Apache Commons HttpClient简介 Apache HttpClient 5简介依赖HttpClient 5 GET 请求HttpClient 5 Fluent GETHttpClient5 GET 请求参数HttpClient 5 POST 请求HttpClient 5 Fluent POSTHttpClient5 POST JSON 参数HttpClient 5 设…

什么是地理信息系统(GIS),它能为我们做什么?

当您准备从事GIS相关职业或准备建设一个GIS相关的系统时&#xff0c;您需要对GIS有一个大概的整体了解。这篇文章很适合您从宏观了解GIS当前的整体情况及发状况&#xff01;希望这篇文章对您有所帮助&#xff01; 什么是地理信息系统&#xff1f; GIS 代表地理信息系统。…

linux时间同步工具chrony的配置和时间设置的相关说明

目录 目录 介绍 1.搭建ntp服务器 2.配置ntp客户端 3.其他设置 4.客户端无法进行时间同步 介绍 目前比较流行的时间同步工具有ntpd和chrony&#xff0c;ntpd采用123/UDP端口通信&#xff0c;chrony采用323/UDP端口通信。Centos7以上版本默认安装chrony服务来同步时间&#x…