nyist 297 GoroSort

nyist 297 GoroSort

​​#include #include using namespace std;const int N=1e3+10;bool vis[N];int a[N];double jie(int x){ double ans=1.0; for(int i=1;i<=x;i++){ ans=ans*i; } return ans;}int main(){ int t,ca=1,n; cin>>t; while(t--){ memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); double ans=0.0; for(int i=1;i<=n;i++){ if(vis[a[i]]==0&&a[i]!=i) { int dex=i,r=0; while(!vis[a[dex]]){ vis[a[dex]]=1; r++; dex=a[dex]; } ans=ans+jie(r); } } printf("Case #%d: %.6lf\n",ca++,ans); } return 0;}

果断WA

对每一个子集进一步深入分析，操作次数还可以更少：

对于2、1的2元素子集该是2个操作，这没有什么质疑的。那么对于3、1、2的子集呢？

成功的概率，共有4种结果。

所以，得到上诉期望。

同样，对于4个元素的集合：

结果就是

发现规律，结果就该是不在本位置上的元素的个数.

#include #include #include using namespace std;int main(){ int t,ca=1,n; cin>>t; while(t--){ scanf("%d",&n); double ans=0.0; int t=0; for(int i=1;i<=n;i++) { scanf("%d",&t); if(t!=i) ans++; } printf("Case #%d: %.6lf\n",ca++,ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。