1 P7874 「SWTR-07」My rating is -32

• 题目链接：https://www.luogu.com.cn/problem/P7874

2 题目描述

时间限制 \(200ms\) | 空间限制 \(16MB\)

将 \(1\sim n\) 不重不漏地分进 \(k\) 个集合 \(S_1,S_2,\cdots,S_k\) 中，满足相邻的数不在同一集合且 \(|S_i|>0\) 。求

\(\sum_{i=1}^k a[{\min_{j\in S_i}j}]\)

的最大值，其中 \([]\) 表示下标。

数据范围：

对于 \(100\%\) 的数据，\(2 \leq k \leq n \leq 10^4\)，\(0 \leq a_i \leq 10^9\)，\(T=10\)。

3 题解

考虑贪心。

容易发现，如果没有相邻的条件，答案就是第一个数加上剩下的前 \(k - 1\) 大数的和。

这是因为我们可以先将所有的数放到一个集合里，然后将前 \(k - 1\) 大的数放到剩余的 \(k - 1\) 个集合中，此时由于这些集合都只有一个元素，所以取得的值就是那个元素。

考虑相邻的条件。容易发现此时我们可以将所有的下标按照奇偶分类，分别放入前两个集合中，然后再从这两个集合中取出剩余的前 \(k- 2\) 大的数。

所以答案就是前两个数加上剩余数中前 \(k - 2\) 的数的和，用优先队列维护即可。

时间复杂度为 \(O(n\log_2n)\)，可以通过本题。

4 代码（空格警告）：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N = 1e4 + 10;
#define int long long
int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
int T, n, k, ans, cnt;
int a[N];
signed main()
{
    T = read(), T = read();
    while (T--)
    {
        cnt = 0;
        priority_queue<int> q;
        n = read(), k = read();
        for (int i = 1; i <= n; i++) a[i] = read();
        ans = a[1] + a[2];
        for (int i = 3; i <= n; i++) q.push(a[i]);
        k -= 2;
        while (q.size() && cnt < k)
        {
            int x = q.top();
            q.pop();
            ans += x;
            cnt++;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

欢迎关注