bzoj 1119 [POI2009]SLO && bzoj 1697 [Usaco2007 Feb]Cow Sorting牛排序—

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1119

　　　https://www.lydsy.com/JudgeOnline/problem.php?id=1697

先找到置换的循环节。发现对于同一个循环节里的元素，可以找一个代价最小的元素，用它把所有元素换到位置上。

每次交换一定有一个元素到自己的位置上了（不然不优）；最后一次是两个元素都弄好了；所以一共是 ( n-1 ) 次。其中，每个元素贡献一次，剩下的 2*(n-1) - n 次贡献就可以选择代价最小的那个元素了。

还以为这样就是最优的。

然而其实还可以在循环节外面找一个最小的元素来和自己换。这样的话除了第一次把这个外面的元素换进循环里，剩下每一次交换都有一个元素到了它应该在的位置，所以一共是 ( n+1 ) 次。其中，每个元素贡献一次，被换出去的元素贡献两次，换进来（最后又换出去）的元素贡献 2*(n+1)-n-1 次。和上面情况取 min 即可。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e6+,M=;

int n,w[N],a[N],b[N],tot; ll ans;

bool vis[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

ll Mn(ll a,ll b){return a<b?a:b;}

int main()

{

  n=rdn();  int tmn=M;

  for(int i=;i<=n;i++)w[i]=rdn(),tmn=Mn(tmn,w[i]);

  for(int i=;i<=n;i++)a[i]=rdn();

  for(int i=;i<=n;i++)b[rdn()]=i;

  for(int i=;i<=n;i++)

    if(!vis[i])

      {

    int cr=i,mn=M;ll sm=; tot=;

    while(!vis[cr])

      {

        tot++; vis[cr]=;

        mn=Mn(mn,w[a[cr]]); sm+=w[a[cr]];

        cr=b[a[cr]];

      }

    ans+=Mn((ll)mn*(tot-)+sm-mn,(ll)tmn*(tot+)+sm+mn);

      }

  printf("%lld\n",ans);

  return ;

}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=1e4+,M=1e5+;

int n,a[N],b[N],c[M],ans;

bool vis[N];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

  while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}

  while(ch>=''&&ch<='') ret=ret*+ch-'',ch=getchar();

  return fx?ret:-ret;

}

int Mn(int a,int b){return a<b?a:b;}

int main()

{

  n=rdn(); int tmn=M;

  for(int i=;i<=n;i++)a[i]=rdn(),tmn=Mn(tmn,a[i]);

  for(int i=;i<=n;i++)b[i]=a[i];

  sort(b+,b+n+);

  for(int i=;i<=n;i++)c[b[i]]=i;

  for(int i=;i<=n;i++)

    if(!vis[i])

      {

    int cr=i,tot=,mn=M,sm=;

    while(!vis[cr])

      {

        tot++; vis[cr]=;

        mn=min(mn,a[cr]); sm+=a[cr];

        cr=c[a[cr]];

      }

    ans+=Mn( mn*(tot-)+sm-mn,tmn*(tot+)+sm+mn );

      }

  printf("%d\n",ans);

  return ;

}

巴特西

bzoj 1119 [POI2009]SLO && bzoj 1697 [Usaco2007 Feb]Cow Sorting牛排序——思路（置换）

最新文章

热门文章