1 P7874 「SWTR-07」My rating is -32
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;
}