牛客网多校第五场 inv (思维+逆序)

2024-02-18 05:38

本文主要是介绍牛客网多校第五场 inv (思维+逆序),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

链接:https://www.nowcoder.com/acm/contest/143/D
来源:牛客网
 

Kanade has an even number n and a permutation b of all of the even numbers in [1,n]

Let a denote an array [1,3,5....n-1] , now you need to find a permutation of [1,n] satisfy both a and b are subsequence of it and minimize the number of inverse pair of it.

 

输入描述:

The first line has a positive even integer nThe second line has n/2 positive even integers b[i]

输出描述:

Output the number of inverse pair of the permutation you find.

示例1

输入

复制

6
2 6 4

输出

复制

2

说明

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

题意:

给定一个【1,n】里所有偶数的排列,b,其中n为偶数,现在有数组a = 【1,3,5,7,....n-1】,现在要求归并a,b使得逆序对数量最少。

思路:

例如    8 6 4 2

我们考虑每个奇数如何放置。

对于7来说,我们考虑比7大的数,那么就只有8一个,如果我们把7放在8前面,那么7将不会与比她大的数产生逆序。

可是我们还要考虑她和比她小的数产生逆序,那么考虑8的后面,若有比7小的数,那么逆序++,并且由7产生的逆序最多有一个,因为我们总可以把7放在最后。

现在考虑5,比5大的数就有两个了,那么由5产生的逆序最多为两个。我们考虑 8 6 的后面,如果没有比5小的数,可以把5放在8,6前面,逆序为0,若果有一个逆序为1,否则取最多2.

由上面的分析可以看出,对于每个奇数,我们考虑比她大的偶数的个数假设为x,那么该奇数最多产生x对逆序,如果,比他大的数可以向后匹配比这个奇数小的数,假设可以匹配出y对来,那么该奇数逆序的贡献为min(x,y);

对于 8 6 4 2 来说考虑5    (8,4),(6,2) 两对,8,6有两个,故而 x=y=2;

那么如何统一计算结果呢????

如果单单考虑5, 遇到8>5 我们可以先存起来,6>5存起来,4<5 取出来8凑一对,2<5取出6凑一对。

设最终逆序为ans = 0;

若统一考虑所有情况。我们可以考虑优先队列来存,

8入队              8 并不小于对中最大值继续

6入队              6 < 8 考虑(8,6)这个对可以使7的逆序加一      ans++

                       又因为对于7来说8只能向后匹配一次已经用了,可是对于小于6的数来说(8,6)的匹配对他们没有任何影响,那                         8 该何去何从 ? 很简单,只要扔掉8,加入一个6就好了,6 肯定不会对7的结果产生影响了,但是可以对剩下的                           产生影响。

                       此时队列就有 6 6,两个6

4入队             4 < 6 一个6出队5这个逆序加一    ans++;

2入队             2 < 6 一个6出队3,5逆序加一     ans+=2;

emmmmm 代码就很简单了,,,

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+7;
int a[maxn],tree[maxn];
int n;int lowbit(int x)
{return x&(-x);
}void add(int x,int v)
{for(;x <= n; x+=lowbit(x))tree[x]+=v;
}int sum(int x)
{int ans = 0;for(;x >= 1; x-=lowbit(x))ans+=tree[x];return ans;
}
int main()
{scanf("%d",&n);for(int i = 0; i < n/2; i++){scanf("%d",&a[i]),a[i]/=2;}long long ans = 0;for(int i = 0; i < n/2; i++){ans+=i-sum(a[i]),add(a[i],1);}priority_queue<int>pq;for(int i = 0; i < n/2; i++){pq.push(a[i]);if(pq.top() > a[i]){ans += pq.top()-a[i];pq.pop();pq.push(a[i]);			}}cout << ans <<endl;return 0;
}

 

这篇关于牛客网多校第五场 inv (思维+逆序)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/720204

相关文章

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

颠覆你的开发模式:敏捷思维带来的无限可能

敏捷软件开发作为现代软件工程的重要方法论,强调快速响应变化和持续交付价值。通过灵活的开发模式和高效的团队协作,敏捷方法在应对动态变化和不确定性方面表现出色。本文将结合学习和分析,探讨系统变化对敏捷开发的影响、业务与技术的对齐以及敏捷方法如何在产品开发过程中处理持续变化和迭代。 系统变化对敏捷软件开发的影响 在敏捷软件开发中,系统变化的管理至关重要。系统变化可以是需求的改变、技术的升级、

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

牛客小白月赛100(A,B,C,D,E,F三元环计数)

比赛链接 官方讲解 这场比较简单,ABC都很签到,D是个不太裸需要预处理的 B F S BFS BFS 搜索,E是调和级数暴力枚举,F是三元环计数。三元环考的比较少,没见过可能会偏难。 A ACM中的A题 思路: 就是枚举每个边变成原来的两倍,然后看看两短边之和是否大于第三边即可。 不能只给最短边乘 2 2 2,比如 1 4 8 这组数据,也不能只给第二短边乘 2 2 2,比

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

【Hdu】Minimum Inversion Number(逆序,线段树)

利用线段树在nlogn的时间复杂度内求一段数的逆序。 由于给的序列是由0 ~ n -1组成的,求出初始的逆序之后可以递推出移动之后的逆序数。 #include<cstdio>#include<iostream>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const in

笔试强训,[NOIP2002普及组]过河卒牛客.游游的水果大礼包牛客.买卖股票的最好时机(二)二叉树非递归前序遍历

目录 [NOIP2002普及组]过河卒 牛客.游游的水果大礼包 牛客.买卖股票的最好时机(二) 二叉树非递归前序遍历 [NOIP2002普及组]过河卒 题里面给的提示很有用,那个马的关系,后面就注意,dp需要作为long的类型。 import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息publ

0906作业+思维导图梳理

一、作业: 1、创捷一个类似于qq登录的界面 1)源代码 #include "widget.h"#include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget){ui->setupUi(this);//QPushbutton:登录、退出this->join = new QP

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

[机缘参悟-222] - 系统的重构源于被动的痛苦、源于主动的精进、源于进化与演进(软件系统、思维方式、亲密关系、企业系统、商业价值链、中国社会、全球)

目录 前言:系统的重构源于被动的痛苦、源于主动的精进、源于进化与演进 一、软件系统的重构 1、重构的定义与目的 2、重构的时机与方法 3、重构的注意事项 4、重构的案例分析 二、大脑思维的重构 1、大脑思维重构的定义 2、大脑思维重构的方法 3、大脑思维重构的挑战与前景 三、认知的重构 1、定义 2、目的 3、方法 四、实例 五、总结 四、婚姻家庭的重构 1、婚