P2127 序列排序 题解

· · 题解

题目传送门

更好的阅读体验？

前置知识

并查集

建议先完成这道题

分析

首先构造一组数据：

3
2 3 1

我们发现如果想让整个序列升序排序，需要将当前 1 移动至当前 2 的位置，将当前 2 移动至当前 3 的位置，而当前 3 的位置需要移动至当前 1 的位置，也就是说，这些移动构成了一个环！

因此我们可以用并查集维护这样一个环，而最小代价则是处理每个环的最小代价之和。

对于每个环，我们需要维护 4 个值：

  1. 这个环的根节点
  2. 这个环中的最小值
  3. 这个环的权值之和
  4. 这个环的节点数量

对于每个环的最小代价，我们需要讨论两种情况：

1. 运用环内最小值进行交换

用 环内最小值交换节点数量减一次，再加上除这个环中的最小值之外其余节点的权值之和，就是这个环运用环内最小值进行交换的代价。

具体表示

(people[i]-1)*minn[i]+sum[i]-minn[i]

2. 运用环外最小值进行交换

首先将环内最小值与环外最小值进行交换，再用 环外最小值交换节点数量减一次，再加上除这个环中的最小值之外其余节点的权值之和，最后将环内最小值与环外最小值进行交换回来，就是这个环运用环外最小值进行交换的代价。

具体表示

(people[i]-1)*mina+sum[i]-minn[i]+2*(mina+minn[i])

代码

  #include<bits/stdc++.h>
  #define int long long
  using namespace std;
  inline char gc(){
      static char buf[1000010],*p1=buf,*p2=buf;
      return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000010,stdin),p1==p2)?EOF:*p1++;
  }
  inline int read(){
      register int x=0,f=0;
      static char s=gc();
      while(s<'0'||s>'9')f|=s=='-',s=gc();
      while(s>='0'&&s<='9'){
          x=(x<<3)+(x<<1)+(s^48);s=gc();
      }return f?-x:x;
  }
  inline void write(register int x){
      if(x<0)putchar('-'),x=-x;
      if(x>9)write(x/10);putchar(x%10^48);
  }
  int n,sum[1000005],minn[1000005],ans,father[1000005],people[1000005],mina=INT_MAX;
  struct nobe{
      int id,val;
      friend bool operator<(nobe x,nobe y){
          return x.val<y.val;
      }
  }a[1000005];
  int findset(int x){
      if(father[x]==x){
          return x;
      }
      return father[x]=findset(father[x]);
  }//并查集寻找根节点操作
  signed main(){
      n=read();
      for(int i=1;i<=n;i++){
          a[i].val=read();
          father[i]=a[i].id=i;//这个环的根节点
          minn[i]=sum[i]=a[i].val;//这个环中的最小值，这个环的权值之和
          people[i]=1;//这个环的节点数量
          mina=min(mina,a[i].val);//环外最小值
      }
      sort(a+1,a+n+1);
      for(int i=1;i<=n;i++){
          if(a[i].id!=i){//若要构成环
              int x=findset(a[i].id),y=findset(i);
              if(x!=y){
                  father[x]=y;
                  sum[y]+=sum[x];
                  people[y]+=people[x];
                  minn[y]=min(minn[y],minn[x]);//并查集合并操作
              }
          }
      }
      for(int i=1;i<=n;i++){
          if(father[i]==i){
              ans+=min((people[i]-1)*mina+sum[i]-minn[i]+2*(mina+minn[i]),(people[i]-1)*minn[i]+sum[i]-minn[i]);
          }//求每个环的最小代价
      }
      write(ans);
      return 0;
  }

总结

分析 难度
思维难度 紫
代码难度 绿
算法难度 橙
分析难度 蓝
综合评估 蓝

题外话

这道题作为我们模拟赛的 T2，在比赛中竟然没有人 AC ，这是多么恐怖！

这道题主要考察题目转化，代码实现与知识点考察并不难，偏向国外的思维题类型，而不像国内某些只会出数据结构。 (我没有针对 Ynoi)

只要思维偏难，考试时就没人做对，可见我们的思维漏洞与国外的 OIer 还差距很远，我们更应该加强锻炼自己的思维，才能真正进步成一个好的 OIer!