建网站要花多少钱,定制软件开发,网站seo网络优化,做店标 做店招的网站题意
定义F(n,k)表示#xff11;#xff0d;#xff4e;的数列中以#xff4b;为子集总个数的最小值 现有#xff21;#xff0c;#xff22;数组 让我们重新排列#xff21; 使得sigma[1 len]F(ai,bi)的数学期望最大
分析
题目看上去有点绕 但从期望上分析下其…题意
定义F(n,k)F(n,k)表示的数列中以为子集总个数的最小值 现有数组 让我们重新排列 使得sigma[1 len]F(ai,bi)sigma[1 ~ len]F(ai,bi)的数学期望最大
分析
题目看上去有点绕 但从期望上分析下其实就能发现 本题再的的排列中求个元素的子集最小数的数学期望应该是 X1∗C(n−1,k−1)/C(n,k)2∗C(n−2,k−1)/C(n,k)...k∗C(k,k−1)/C(n,k)X= 1*C(n-1,k-1)/C(n,k)+2*C(n-2,k-1)/C(n,k)+...+k*C(k,k-1)/C(n,k) 分别是最小数结果为的情况的情况的情况…的情况 那么知道了这一点 也就是求让数组重新排列后求得的最大 那么如何使上式最大呢 这里面是定值 也就是让尽可能大 那么也就是说把最大的去搭配尽可能小的 那么排序一下不就搞定了 #includebits/stdc.h
using namespace std;
const int maxn 2e510;
struct node{int id,x;
}b[maxn];int a[maxn],ans[maxn];
bool cmp(node a,node b){return a.xb.x;
}
int main()
{int n;scanf(%d,n);for(int i1;in;i)scanf(%d,a[i]);for(int i1;in;i)scanf(%d,b[i].x),b[i].id i;sort(a1,a1n);sort(b1,b1n,cmp);for(int in;i1;i--){ans[b[i].id]a[i];}for(int i1;in;i)printf(%d%c,ans[i],in?\n: ); return 0;
}
