当前位置:网站首页>C. Omkar and Baseball
C. Omkar and Baseball
2022-08-09 21:55:00 【秦小咩】
C. Omkar and Baseball
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Patrick likes to play baseball, but sometimes he will spend so many hours hitting home runs that his mind starts to get foggy! Patrick is sure that his scores across nn sessions follow the identity permutation (ie. in the first game he scores 11 point, in the second game he scores 22 points and so on). However, when he checks back to his record, he sees that all the numbers are mixed up!
Define a special exchange as the following: choose any subarray of the scores and permute elements such that no element of subarray gets to the same position as it was before the exchange. For example, performing a special exchange on [1,2,3][1,2,3] can yield [3,1,2][3,1,2] but it cannot yield [3,2,1][3,2,1] since the 22 is in the same position.
Given a permutation of nn integers, please help Patrick find the minimum number of special exchanges needed to make the permutation sorted! It can be proved that under given constraints this number doesn't exceed 10181018.
An array aa is a subarray of an array bb if aa can be obtained from bb by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.
Input
Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1001≤t≤100). Description of the test cases follows.
The first line of each test case contains integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of the given permutation.
The second line of each test case contains nn integers a1,a2,...,ana1,a2,...,an (1≤ai≤n1≤ai≤n) — the initial permutation.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case, output one integer: the minimum number of special exchanges needed to sort the permutation.
Example
input
Copy
2 5 1 2 3 4 5 7 3 2 4 5 1 6 7
output
Copy
0 2
Note
In the first permutation, it is already sorted so no exchanges are needed.
It can be shown that you need at least 22 exchanges to sort the second permutation.
[3,2,4,5,1,6,7][3,2,4,5,1,6,7]
Perform special exchange on range (1,51,5)
[4,1,2,3,5,6,7][4,1,2,3,5,6,7]
Perform special exchange on range (1,41,4)
[1,2,3,4,5,6,7][1,2,3,4,5,6,7]
=========================================================================
显然递增的肯定是0
如果有一段连续的,其中每个数字都不在原位置,那么把这些数字归到原位置那么就一定不会跟原来的顺序产生任何重叠,也就是耗费1
要是有多段连续的,先将整个变成不同于原来的,也不同于递增的,再将其变成递增的
这里不太好证明为什么一定会存在一个介于两者之间,不同与二者的排列,不妨进行dfs验证一下5
的
# include<iostream>
# include<string.h>
# include<vector>
using namespace std;
int a[200000+10];
int main ()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x==i)
a[i]=1;
else
a[i]=0;
}
int cnt=0;
a[n+1]=1;
for(int i=1;i<=n;i++)
{
if(a[i]==0&&a[i+1])
{
cnt++;
}
}
cout<<min(cnt,2)<<endl;
}
return 0;
}
边栏推荐
猜你喜欢
AI+Medical: Using Neural Networks for Medical Image Recognition and Analysis
MLOps的演进历程
大型分布式存储方案MinIO介绍,看完你就懂了!
十步以内,用小程序快速生成App!
Flask's routing (app.route) detailed
Leetcode.25 K个一组翻转链表(模拟/递归)
肝通宵写了三万字把SQL数据库的所有命令,函数,运算符讲得明明白白讲解,内容实在丰富,建议收藏+三连好评!
腾讯继续挥舞降本增效“大刀”,外包员工免费餐饮福利被砍了
[Microservice~Nacos] Nacos service provider and service consumer
从源码方面来分析Fragment管理中 Add() 方法
随机推荐
开发者必备:一文快速熟记【数据库系统】和【软件开发模型】常用知识点
AI+Medical: Using Neural Networks for Medical Image Recognition and Analysis
孙正义亏掉1500亿:当初投贵了
Arcgis工具箱无法使用,显示“XML包含错误“的解决方法
金山云地震,震源在字节?
Flask入门学习教程
2022 首期线下 Workshop!面向应用开发者们的数据应用体验日来了 | TiDB Workshop Day
Basic operations of openGauss database (super detailed)
Flask introductory learning tutorial
重装系统后新建文本文档打不开怎么办
MLOps的演进历程
Quotefancy ,提供鼓舞人心语录的壁纸网站 - 倾城之链
【测试】语句覆盖,判定覆盖,条件覆盖,路径覆盖
Leetcode 93 IP addresses
AI Knows Everything: Building and Deploying a Sign Language Recognition System from Zero
README_Albumentations
SQLi-LABS Page-2 (Adv Injections)
2.1.5 大纲显示问题
Rust 解引用
Liver all night to write a thirty thousand - word all the commands the SQL database, function, speaks clearly explain operators, content is rich, proposal collection + 3 even high praise!