Codeforces C. Omkar and Baseball (思维 / 特殊排序 / 分类讨论) (Round #655 Div.2)

本文主要是介绍Codeforces C. Omkar and Baseball (思维 / 特殊排序 / 分类讨论) (Round #655 Div.2),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门

题意: 有一个含有n个元素的初始序列,现在定义一种排序方法——可以以任意顺序移动一个连续区间的元素,但每个元素移动和不能与移动前处于同一个位置。试问知识多少次可以将原数组排列成1~n的升序数列?
在这里插入图片描述

思路:

  • 因为排序方法是任意移动排序的,所有我们可以通过区间数来处理。找出位置不符的小区间cnt有多少个。
  • 若cnt == 0,说明原数组就是1~n的升序数列。
  • 若cnt == 1,说明只需要通过一次就能将这个这个子段排序正确。
  • 若cnt >= 2,说明想要少次数的排序好整个序列,就需要移动一下中间正确位置的元素;但总体来说都可以通过第一次排序将原数组变成只有两个位置不符的情况,再排序一次就是正确的数列了。

代码实现:

#include<bits/stdc++.h>
#define endl '\n'
#define null NULL
#define ll long long
#define int long long
#define pii pair<int, int>
#define lowbit(x) (x &(-x))
#define ls(x) x<<1
#define rs(x) (x<<1+1)
#define me(ar) memset(ar, 0, sizeof ar)
#define mem(ar,num) memset(ar, num, sizeof ar)
#define rp(i, n) for(int i = 0, i < n; i ++)
#define rep(i, a, n) for(int i = a; i <= n; i ++)
#define pre(i, n, a) for(int i = n; i >= a; i --)
#define IOS ios::sync_with_stdio(0); cin.tie(0);cout.tie(0);
const int way[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
using namespace std;
const int  inf = 0x7fffffff;
const double PI = acos(-1.0);
const double eps = 1e-6;
const ll   mod = 1e9 + 7;
const int  N = 2e5 + 5;int t, n;
int a[N];signed main()
{IOS;cin >> t;while(t --){cin >> n;int cnt = 0;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] != i && a[i - 1] == i - 1){
//                cout << "i+:" << i << " " << cnt << endl;cnt ++;}}
//        cout << "cnt:" << cnt << endl;if(!cnt) cout << 0 << endl;else if(cnt == 1) cout << 1 << endl;else cout << 2 << endl;}return 0;
}

这篇关于Codeforces C. Omkar and Baseball (思维 / 特殊排序 / 分类讨论) (Round #655 Div.2)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int

Perl 特殊变量详解

《Perl特殊变量详解》Perl语言中包含了许多特殊变量,这些变量在Perl程序的执行过程中扮演着重要的角色,:本文主要介绍Perl特殊变量,需要的朋友可以参考下... perl 特殊变量Perl 语言中包含了许多特殊变量,这些变量在 Perl 程序的执行过程中扮演着重要的角色。特殊变量通常用于存储程序的

基于人工智能的图像分类系统

目录 引言项目背景环境准备 硬件要求软件安装与配置系统设计 系统架构关键技术代码示例 数据预处理模型训练模型预测应用场景结论 1. 引言 图像分类是计算机视觉中的一个重要任务,目标是自动识别图像中的对象类别。通过卷积神经网络(CNN)等深度学习技术,我们可以构建高效的图像分类系统,广泛应用于自动驾驶、医疗影像诊断、监控分析等领域。本文将介绍如何构建一个基于人工智能的图像分类系统,包括环境

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

BUUCTF(34)特殊的 BASE64

使用pycharm时,如果想把代码撤销到之前的状态可以用 Ctrl+z 如果不小心撤销多了,可以用 Ctrl+Shift+Z 还原, 别傻傻的重新敲了 BUUCTF在线评测 (buuoj.cn) 查看字符串,想到base64的变表 这里用的c++的标准程序库中的string,头文件是#include<string> 这是base64的加密函数 std::string

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m