【CodeForces】841C. Leha and Function（Codeforces Round #429 (Div. 2)）

【题意】定义函数F(n,k)为1~n的集合中选择k个数字，其中最小数字的期望。

给定两个数字集A,B，A中任意数字>=B中任意数字，要求重组A使得对于i=1~n,sigma(F(Ai,Bi))最大。

【算法】数学结论+数学期望+排序

【题解】很无奈，这题放在div2 C，难以推导的期望公式，广为人知的结论，容易观察样例得出的做法，都体现了这道题的不合理性。

F(n,k)=(n+1)/(k+1)

公式推导可能触及我的知识盲区了QAQ

得到公式后，显然要求k尽可能小，n尽可能大，经验告诉我们随着两数差增大，两数相除的结果急速增大（相对的，两数差减小，两数相乘的结果急速增大）。

所以排序后反着相对就可以了，而这个结论可以通过观察样例很快得出。

#include<cstdio>

#include<cstring>

#include<cctype>

#include<cmath>

#include<algorithm>

#define ll long long

using namespace std;

int read()

{

    char c;int s=,t=;

    while(!isdigit(c=getchar()))if(c=='-')t=-;

    do{s=s*+c-'';}while(isdigit(c=getchar()));

    return s*t;

}

/*------------------------------------------------------------*/

const int inf=0x3f3f3f3f,maxn=;

int n,a[maxn],c[maxn];

struct cyc{int num,ord;}b[maxn];

bool cmp(cyc a,cyc b)

{return a.num<b.num;}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)a[i]=read();

    for(int i=;i<=n;i++){

        b[i].num=read();

        b[i].ord=i;

    }

    sort(b+,b+n+,cmp);

    sort(a+,a+n+);

    for(int i=;i<=n;i++)c[b[i].ord]=a[n-i+];

    for(int i=;i<=n;i++)printf("%d ",c[i]);

    return ;

}

巴特西

【CodeForces】841C. Leha and Function（Codeforces Round #429 (Div. 2)）

最新文章

热门文章