题意:已知n个数,分别取n1,n2个数字,使得sum1/n1+sum2/n2的值最大。
思路:贪心,如果n1小,那么n1先取最大的,否则n2先取。证明过程如下// (s2-s2’)括号忘加了抱歉
数据分析:1 ≤ n, n1, n2 ≤ 100 000, n1 + n2 ≤ n,1 ≤ ai ≤ 100 000
复杂度分析:O(n)
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+50;
int a[maxn];
bool cmp(const int a,const int b)
{return a>b;}
int main(void)
{
int n,n1,n2;
cin >> n >> n1 >>n2;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n,cmp);
// for(int i=1;i<=n;i++)
// printf("%d ",a[i]);
double ans=0;
if(n1<n2)
{
ll sum=0;//注意爆int的情况,所以sum开ll
for(int i=1;i<=n1;i++)
sum+=a[i];
ans+=1.0*sum/n1;
sum=0;
for(int i=n1+1;i<=n1+n2;i++)
sum+=a[i];
ans+=1.0*sum/n2;
}
else
{
ll sum=0;
for(int i=1;i<=n2;i++)
sum+=a[i];
ans+=1.0*sum/n2;
sum=0;
for(int i=n2+1;i<=n2+n1;i++)
sum+=a[i];
ans+=1.0*sum/n1;
}
printf("%.8f\n",ans);
}