当前位置:网站首页>Exchange bottles (graph theory + thinking)
Exchange bottles (graph theory + thinking)
2022-07-06 03:44:00 【AC__ dream】
sample input 1:
5
3 1 2 5 4
sample output 1:
3
sample input 2:
5
5 4 3 2 1
sample output 2:
2
The idea of this topic is difficult to think about , It is a problem combined with graph theory , We put this n A position can be regarded as n A little bit , For the first i The value of a point a[i], Jean di i Point to point a[i] A dot with a directed edge represents the i The final position of the value at point is a[i] A little bit , Because each point will only have a final position and the position will only be the final position of a point , So after connecting the edges according to the above method, there will only be one out edge and one in edge for each point , That is, it will form several rings , Follow the example first 1 Draw edges and analyze :
This is the graph built according to the above method , Now let's take a look at what changes will happen when we build a map after exchanging two points
At this time, the discussion should be divided into two situations , One is to exchange two points in a ring , The other is that the two points exchanged are located in two rings
Case one :( The two points of exchange are located in a ring , such as 1,2 Point on position )
be 1 The point on the position will point to 2 The point pointed by the position point , That is to say 1, and 2 The position will point to 1 The point the position points to , That is to say 3, So we'll find out 1 Forming a self ring , So the number of rings decreases 1
The second case :( The two points of exchange are located on two different rings , such as 1,5 Point on position )
be 1 The point on the position will point to 5 The point pointed by the position point , That is to say 4, and 5 The position will point to 1 The point the position points to , That is to say 3, In this way, we will find that the ring of these two points becomes a big ring , That is, the number of rings is reduced 1
Through the analysis of these two situations , We will find that if two points of the exchange are in a ring , Then the number of rings decreases 1, If two points of the exchange are on two different rings , Then the number of rings decreases 1, And our final situation is that all points form a self ring , That is, the number of rings is n, So we should exchange two points in a ring at a time to increase the number of rings 1. So the answer is n- At first, the number of rings
How to calculate the number of rings , A clever method is used here , Refer to code for details :
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=10003;
int a[N];
bool vis[N];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
int cnt=0;
for(int i=1;i<=n;i++)
{
if(!vis[i])
{
cnt++;
int t=i;
while(!vis[t])
{
vis[t]=true;
t=a[t];
}
}
}
printf("%d",n-cnt);
return 0;
}
边栏推荐
- Blue style mall website footer code
- 记录一下逆向任务管理器的过程
- SAP ALV color code corresponding color (finishing)
- [optimization model] Monte Carlo method of optimization calculation
- cookie,session,Token 这些你都知道吗?
- ASU & OSU | model based regularized off-line meta reinforcement learning
- Four logs of MySQL server layer
- [matlab] - draw a five-star red flag
- Esbuild & SWC: a new generation of construction tools
- Svg drag point crop image JS effect
猜你喜欢
2.2 fonctionnement stm32 GPIO
UDP reliable transport protocol (quic)
RT-Thread--Lwip之FTP(2)
教你用Pytorch搭建一个自己的简单的BP神经网络( 以iris数据集为例 )
Cubemx 移植正点原子LCD显示例程
Idea push rejected solution
Esbuild & SWC: a new generation of construction tools
Princeton University, Peking University & UIUC | offline reinforcement learning with realizability and single strategy concentration
简易博客系统
2.1 rtthread pin device details
随机推荐
给新人工程师组员的建议
Mysqldump data backup
Indicator system of KQI and KPI
On Data Mining
施努卡:3d视觉检测应用行业 机器视觉3d检测
The solution of permission denied (750 permissions should be used with caution)
Pytorch load data
记录一下逆向任务管理器的过程
Four logs of MySQL server layer
RT thread -- FTP of LwIP (2)
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
EDCircles: A real-time circle detector with a false detection control 翻译
Computer graduation project asp Net fitness management system VS development SQLSERVER database web structure c programming computer web page source code project
Microkernel structure understanding
[matlab] - draw a five-star red flag
Deno介绍
遥感图像超分辨重建综述
WPF效果第一百九十一篇之框选ListBox
[slam] lidar camera external parameter calibration (Hong Kong University marslab) does not need a QR code calibration board
Safety science to | travel, you must read a guide