今天收获颇丰,长春邀请赛我们至少能开4题,题目思维不难,实现上细节比较多。
今天单切一道1400div3的E题,有点guess的成分;
题目:https://codeforces.com/contest/2033/problem/E
题目大意,给你一个数组,若数组第i位上是i或者第i位和第j位分别是j和i(即交换位置),那么这个数组好;
我们可以选择两个索引i和j并交换ai和aj,这是一次操作,求最少几次操作使得数组好。
对于ai == i,我们不必操作,观察发现,找数字时必然会循环,对于一定的循环次数貌似也有最小操作次数;
举例发现循环次数x和操作次数y的关系:
x y
1 0
2 0
3 1
4 1
5 2
6 2
猜测是y = (x - 1) / 2;
提交发现猜测正确。
另外,以后写题一定加输入输出流控制,今天想了好久才发现是没加这个导致超时
代码:
———————————
include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000010;
int a[N];
bool vis[N];
int dfs(int i,int k)
{
if (vis[i])
{
return k;
}
vis[i] = true;if (a[i] == i)
{return 0;
}
else
{return dfs(a[i], k + 1);
}
}
void solve()
{
int n,ans = 0;
cin >> n;
for(int i = 1;i<=n;i++)
{
cin >> a[i];
vis[i] = 0;
}
for(int i = 1;i<=n;i++)
{
ans += (dfs(i,0) - 1) / 2;
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
return 0;
}