闲人の题解 P7878

violet

文章标签

首页

归档

标签

关于

友人帐

载入天数...

载入时分秒...

总访问量: | 访问人数:

2021-11-20

5 min read

题解

闲人の题解 P7878

Step1：题目简化&粗略分析

与我以往写的题解不同，这一篇题解的第一个部分不再是《题目描述》，而是《题目简化&分析》，因为在我看来此题最大的障碍在于题目的理解。

首先，让我们理解一下什么叫做“用同一账号连续发多个帖子”。这其中有个很重要的一点，这会影响到我们后续的做题，注意此处的“连续”，设想一个问题，如果我发的所有帖子是不连续的（也就是说我在几个账号上循环发帖），那么就不存在同一账号上的“连续的多个帖子”了。
其次，在理解了上一个问题之后再来看一下“该账号的安全指数会减小这两篇帖子安全指数的较小值”这句话做何理解（怎么感觉再讲阅读理解？）。其实很容易弄懂，这句话是指在同一账号中的连续帖子之间相邻连个帖子的最小值就是这个账号的风险，把这些值累加起来，第一篇帖子的安全系数减去累加起来的值就是这个账号的安全指数。

Step2：题目详细分析

在理解了第一部分的内容后就开始对题目进行一个较为深入的解析。

Step2_1：关于安全指数的来源

来源有二：其一，是本账号的第一篇帖子的安全指数。其二在后续发帖过程中所损失的安全指数。

Step2_2：如何使安全指数最大化

首先不难发现，总有一个账号的第一篇帖子是所有帖子的第一篇，应为所有帖子的的发帖顺序是固定的，只是在那个账号发事不固定的。
其次，根据 Step1_1 中提到的：“如果我发的所有帖子是不连续的（也就是说我在几个账号上循环发帖），那么就不存在同一账号上的‘连续的多个帖子’。”可以得出所有会损失安全值得操作会在第二个账号发了一个帖子后结束。
接下来，如果在用第二个账号发帖之后还有多余的账号，就可以用账号来发剩下帖子中价值最大的贴子以获取最大的收益。
最后一点，也是本题的关键：确定第二个账号发的第一个帖子是哪一篇。解决了这个问题，此题就结束了。

Step2_3：如何解决 Step2_2_4 中所提到的问题

设想一个问题，如果前面帖子损失的安全指数已经大于了所有账号第一篇帖子中的最小值，那么我肯定会舍弃这个帖子然后减小前面帖子的损失。

这样的话我们就可以有效的解决 Step2_2_4 中的问题。

代码分析

接下来，只讲我个人的做题方法

先对所有相邻的贴子求一遍最小值，在对最小值求前缀和预处理。
对原来序列排序，找出 $k - 1$ 个最大的帖子（还有一个帖子是所有帖子中的第一个，在 Step2_2_1 中有所讲解，并且记录这些帖子中最靠前的是哪一篇，（记位置为 $first\_where$ ）。
枚举 $2$ 到 $first\_where$ 的每一个帖子作为第二个账号的第一篇帖子所获得的最大收益，求出答案

AC code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define reg register
#define ll long long

using namespace std;

int Time;
int T;
int n, k;

struct Node{
	ll size;
	int where;
}passage[100000 + 10];

ll pre[100000 + 10];
ll pre_[100000 + 10];
ll d[100000 + 10];

bool cmp(Node x, Node y) {return x.size > y.size;}

int main()
{
	scanf("%d", &Time);
	scanf("%d", &T);
	while(T--)
	{
		ll ans = 0, first = 0;
		ll Max = -1e9;
		ll value = 0;
		int first_where = 1e9;
		scanf("%d%d", &n, &k);
		for (reg int i = 1; i <= n; i++)
		{
			scanf("%d", &passage[i].size);
			passage[i].where = i;
			d[i] = pre[i] = passage[i].size;
		}
		first = passage[1].size;
		for (reg int i = 1; i < n; i++) pre[i] = min(passage[i].size, passage[i + 1].size);
		for (reg int i =1; i < n; i++) pre[i] = pre[i] + pre[i - 1];
		for (reg int i = 3; i <= n; i++) pre_[i] = pre[i - 2];
		sort(passage + 2, passage + n + 1, cmp);
		for (reg int i = 2; i <= k; i++) 
			first_where = min(first_where, passage[i].where);
		for (reg int i = 2; i <= k; i++) value += passage[i].size;
		Max = value + first - pre_[first_where];
		for (reg int i = 2; i < first_where; i++)
			Max = max(Max, (first - pre_[i] + d[i] + value - passage[k].size));
		printf("%lld\n", Max);
	}
	return 0;
}