MX Day 8

T1：

做法：

我们可以发现这道题就是要我们删掉几个数剩下m个数，要我们将其两两相加，求最大的和；
所以我们可以想到二分答案的做法
我们二分一个k，将小于等于k/2的数全部找出来，他们是不用删掉的；
我们再枚举这些数之间的那些大于k/2的那些数
如果有加起来小于k的结果，我们就保留；
最后，我们返回留下的数的个数，如果不足m，那么就要增大k，否则减小k

code：

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
// int n;
// vector<int> cur;
int a[1000009];
int u, n, m;
int check(int mid)
{
    vector<int> cur;
    // cur.clear();
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (a[i] * 2 <= mid)
        {
            cur.push_back(i);
        }
    }
    // cout << "siz=" << cur.size() << endl;
    if (cur.empty())
    {
        return false;
    }
    else if (cur.size() == 1)
    {
        // cout << "???\n";
        for (int i = 1; i <= n; i++)
        {
            if (i != cur[0] && a[i] + a[cur[0]] <= mid)
            {
                return 2;
            }
        }
        return 1;
    }
    // else
    // {
    for (int i = 0; i + 1 < cur.size(); i++)
    {
        for (int j = cur[i] + 1; j < cur[i + 1]; j++)
        {
            if (max(a[cur[i]], a[cur[i + 1]]) + a[j] <= mid)
            {
                cnt++;
                break;
            }
        }
    }
    // cout << "cnt=" << cnt << endl;
    for (int i = 1; i < cur[0]; i++)
    {
        if (max(a[cur[0]], a[cur.back()]) + a[i] <= mid)
        {
            // cout << "shuchu=" << cur.size() + cnt + 1 << endl;
            return cur.size() + cnt + 1;
        }
    }
    for (int i = cur.back() + 1; i <= n; i++)
    {
        if (max(a[cur[0]], a[cur.back()]) + a[i] <= mid)
        {
            // cout << "shuchu=" << cur.size() + cnt + 1 << endl;
            return cur.size() + cnt + 1;
        }
    }
    // cout << "shuchu=" << cur.size() + cnt << endl;
    return cur.size() + cnt;
}
signed main()
{
    freopen("necklace.in", "r", stdin);
    freopen("necklace.out", "w", stdout);
    u = read();
    n = read();
    m = read();
    int maxn = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = read();
        maxn = max(maxn, a[i]);
    }
    int l = 1, r = maxn * 2 + 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        // cout << "l=" << l << " r=" << r << " mid=" << mid << endl;
        int ans = check(mid);
        // cout << "now=" << ans << endl
        //      << endl;
        if (ans >= m)
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    cout << l << endl;
    return 0;
}

T2：

做法：

反正这个题的关键点是第一个条件，第二个条件我们可以用DP顺序轻松压过去；
首先，我们设dp[i][j][k]表示前i个点，有j棵树，其中前i个点缺少K个儿子；
之后，就是三种讨论（其中l表示钦定这棵树有几个儿子）:

文章操作

T1：

code：

T2：

相关推荐

评论

MX Day 8