标签归档:置换群

BZOJ1697 Cow Sorting (置换群)

分析可参考 :
http://hzwer.com/3905.html

code:

#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <vector>

using namespace std;

#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;

int pos[100005];
int a[10005];
int vis[10005];

int main() {
  // clock_t start,end;
  // start=clock();
  // freopen("in.txt","r",stdin);
  // freopen("out.txt","w",stdout);
  int n,smallest=100000;
  cin>>n;
  for(int i=1;i<=n;++i){
      cin>>a[i];
      pos[a[i]]=i;
      smallest=min(a[i],smallest);
  }
  sort(a+1,a+1+n);
  int ans=0;
  for(int i=1;i<=n;++i){
      int p=i;
      int len=0,sum=0,minn=a[p];
      while(!vis[p]){
          vis[p]=1;
          sum+=a[p];
          len++;
          minn=min(minn,a[p]);
          p=pos[a[p]];
      }
      if(len) ans+= min(sum+minn+(len+1)*smallest,sum+(len-2)*minn);
  }
  cout<<ans<<endl;
  // end=clock();
  // cout<<"TIME PASSED:"<<end-start<<endl;
  return 0;
}