abc094d<组合数>-526互联

题目

Binomial Coefficients
\(n\)个数中选择两个数作为组合数\(C(m,r)\)的\(m\)和\(r\)，使得组合数的值最大。

思路

首先选择最大的数作为\(m\)；
其次，对于确定的\(m\)，要使得组合数最大，使得\(r\)接近\(\left \lceil \frac{m}{2} \right \rceil\)即可。（即使得\(|a_i - \left \lceil \frac{m}{2} \right \rceil|\)最小者。

代码

点击查看代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using LL = long long;

void solv()
{
    vector<int> a;
    int n, t;
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        cin >> t;
        a.push_back(t);
    }

    sort(a.begin(), a.end());
    int tar = (a.back() + 1) / 2;
    int idx = lower_bound(a.begin(), a.end(), tar) - a.begin();
    
    int l = max(0, idx - 2);
    int r = min(n - 1, idx + 2);
    int min_delta = 2e9, min_idx = -1;
    for (int i = l; i <= r; i ++)
        if (abs(a[i] - tar) < min_delta)
        {
            min_delta = abs(a[i] - tar);
            min_idx = i;
        }

    int ans1 = a.back();
    int ans2 = a[min_idx];

    cout << ans1 << " " << ans2 << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T--)
        solv();
    return 0;
}