返回题解分享
讨论 / 题解分享/ 帖子详情

逆序对期望(结果填空) - 题解

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
double a[60];
double ans,sum;
double check()
{
    double tmp=0;
    for(int i=1;i<=51;i++)
    {
        for(int j=i+1;j<=51;j++)
        {
            if(a[i]>a[j]) tmp++;
        }
    }
    return tmp;
}
void solve()
{
  for(int i=1;i<=51;i++) a[i]=i;
  for(int i=1;i<=51;i++)
  {
      for(int j=i+1;j<=51;j++)
      {
          if(i!=j)
          {
              swap(a[i],a[j]);
              for(int k=1;k<=51;k++)
              {
                  for(int l=k+1;l<=51;l++)
                  {
                      if(l!=k)
                      {
                          sum++;
                          swap(a[k],a[l]);
                          ans+=check();
                          swap(a[k],a[l]);
                      }
                  }
              }
              swap(a[i],a[j]);
          }
      }
  }
  printf("%.2lf %.2lf %.2lf",ans,sum,ans/sum);
}
signed main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  t=1;
  // cin>>t;
  while(t--)
  {
    solve();
  }
  return 0;
}
1 回复 0 转发 0 喜欢 9 阅读
回复 (1)
默认 最新
露米 4 天前
看到你分享的思路了,代码逻辑很清晰。

不过我注意到数组规模是 51,这种多层嵌套循环跑起来可能会比较辛苦,不知道你本地运行出结果大概需要多久?

如果是为了解决这类期望问题,或许可以尝试从“期望的线性性质”入手,看看能不能通过数学推导来简化计算。如果你感兴趣的话,我们可以一起讨论看看有没有更高效的方法 🙂
比如考虑每一对数字在经过操作后成为逆序对的概率,有时候会有意想不到的突破。

如果你在尝试过程中有了新的发现,或者遇到了什么小阻碍,都欢迎随时分享出来。我会在这里一直陪着你一起探索的。
0