AcWing 1361. 三值序列排序
原题链接
中等
作者:
猪啊猪
,
2022-05-10 11:07:08
,
所有人可见
,
阅读 384
重要结论
本题中 图中的环可以拆分为若干两个节点的小环 和 若干所有节点的大环
- 思路来源于y总视频
- 具体证明得用图论知识。早忘光了。可以自己举例几个感受一下。
- 两个节点的小环:交换1次即可归位
- 三个节点的小环:交换2次即可归位
- 做法
- 采用邻接矩阵建图
- 先枚举所有2个结点的小环,再算大环
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 1005;
int a[maxn];
int b[maxn];
int e[4][4]; // 邻接矩阵 记录图 e[1][2]=x 即从1指向2的有x条
// 结论:图中的环可以拆分为若干两个节点的小环 和 若干所有节点的大环
// 具体证明我不会。不过可以举例感受一下。
// 两个节点的小环:交换1次即可归位
// 三个节点的小环:交换2次即可归位
// n个节点的小环:交换n-1次即可归位
int main()
{
int n;
cin>>n;
for(int i=0;i<n;++i)
{
cin>>a[i];
}
memcpy(b,a,n*4);
sort(b,b+n);
// 1. 建图 这么简单的建图我怎么没想到
for(int i=0;i<n;++i)
{
++e[a[i]][b[i]];
}
// for(int i=1;i<=3;++i)
// {
// for(int j=1;j<=3;++j)
// {
// cout<<e[i][j]<<" ";
// }
// cout<<endl;
// }
// cout<<endl;
int ans = 0;
// 2. 枚举所有小环 并去掉
for(int i=1;i<=3;++i)
{
for(int j=i+1;j<=3;++j)
{
int t = min(e[i][j],e[j][i]);
e[i][j] -= t;
e[j][i] -= t;
ans += t;
}
}
// 3. 剩下的只有包含所有节点的>=0条的完整大环
ans += (e[1][2]+e[2][1]) *(3-1); // 3个节点 挪动n-1次,会使得每个节点到自己的位置
cout<<ans<<endl;
}
请问这种思路y总在哪道题中讲过呢
USACO Training辅导课的AcWing 1361. 三值序列排序里讲过。