3136. 指数比例

这个所谓的超出一半还挺坑的，详情见代码

include

using namespace std;
int T;
vector V;
vector V2;

int cmp(double aa,double bb)
{
return aa-bb>0;
}
void solve()
{
int n;
cin>>n;
V.clear();

double sum=0;
for(int i=1;i<=n;i++)
{
double xx;
cin>>xx;
sum+=exp(xx);
V.push_back(xx);
}

V2.clear();
for(int i=0;i0) V2.push_back(V[i]);

sort(V2.begin(),V2.end(),cmp);
for(int i=0;i<V2.size();i++) printf(“%.2f\n”,V2[i]);
return;
}

int main()
{
scanf(“%d”,&T);
for(int step=0;step<T;step++)
{
printf(“case #%d:\n”,step);
solve();
}
return 0;
}

我苦思冥想找不到代码的bug，结果发现是忘了排序，真是被自己蠢哭了23333

已知比率 ratio 为
$$
r(A_i) = \frac{e^{A_i}}{\sum^n_{j=1}e^{A_j}},
$$
令 $\beta = \frac{0.5}{n}$，$\alpha = \sum^n_{i=1}e^{A_i}$（分别是 passing_line 和 overall），符合条件的只要满足：
$$
r(A_i) > \beta
$$
即
$$
A_i > \log (\alpha\beta)
$$
即可。
由于要从大到小输出，必然要排序。这种情况下可以用二分来快速找出范围。

（其实我就是练练写公式，哈哈）

#include <iostream>
#include <cmath>
#include <numeric>
#include <cstdint>
#include <algorithm>
using namespace std;

int main() {
    uint32_t t;
    cin >> t;
    for (uint32_t query = 0; query < t; ++query) {
        printf("case #%u:\n", query);
        uint32_t n;
        cin >> n;
        double nums[50];
        for (uint32_t i = 0; i < n; ++i) {
            cin >> nums[i];
        }
        sort(nums, nums + n);
        auto const passing_line = 0.5 / n;
        auto const overall =
            accumulate(nums, nums + n, 0.0, [](double accum, double num) { return accum + exp(num); });
        auto const threshold = log(overall * passing_line);
        auto r_ed = upper_bound(nums, nums + n, threshold);
        for (auto i = nums + n - 1; i >= r_ed; --i) {
            printf("%.2lf\n", *i);
        }
    }
}