D 无限的韵律源点 (STL_set ,*****)

本文主要是介绍D 无限的韵律源点 (STL_set ,*****)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

Arcaea（韵律源点）是一款著名的音乐游戏（以下简称 arc）。在 arc 中，玩家评分 (PTT) 是 total best 和 recent best 两部分分数维护的所有曲目的单曲评分平均值。

recent best 部分维护的，是你当前时刻下最近游玩的前 ra 首曲目 （包含当前时刻下游玩的曲目）中单曲得分最高的前 rb 首曲目；total best 部分维护的，是你当前时刻下所有已经游玩过的曲目中单曲得分最高的前 b 首曲目。你需要计算在你的游玩过程中，recent best 部分维护的曲目得分之和与 total best 部分维护的曲目得分之和的总和最大值。

形式化地说，给定一个正整数序列 ai(1≤i≤n))，设 Ri 表示 amax⁡(1,i−ra+1),⋯,ai​ 中最大的 min⁡(i,rb) 个数之和，设 Ti表示 a1,⋯ ,ai中最大的  min⁡(i,b) 个数之和。对于 1≤i≤n，求 Ri+Ti 的最大值。 

输入描述:

第一行输入四个整数 n,b,ra,rb(1≤rb≤ra≤n≤2×105,1≤b≤n≤2×105)。分别代表您游玩了 n 首曲目；在计算 total best 部分时，取历史单曲评分最高的 b 首曲目；在计算 recent best 部分时，取历史最近 ra 首曲目中单曲评分最高的 rb 首。第二行输入 n 个整数 ai(0≤ai≤109)，代表了您在 n 个时刻内游玩曲目获得的单曲评分 ，输入的顺序就代表了您游玩的顺序。

输出描述:

输出一行一个整数，表示所求的总和最大值。

示例1

输入

5 2 3 2
1 6 2 3 3

输出

18

说明

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网用 total 表示已经游玩过曲目的序列；用 recent 表示已经游玩过的曲目中，历史最近 rarara 首曲目的序列。时刻 [0,5] 的 total 与 recent 部分维护过程如下：当 t=0，你还没有游玩过曲目，此时 total=[],recent=[],此刻计算得出的 PTT 为 0。当 t=1，你游玩了第一首曲目，获得的单曲得分为 1，此时 total=[(1)],recent=[(1)]，此时的最大总和为 2。当 t=2，你游玩了第二首曲目，获得的单曲得分为 6，此时 total=[(1),(6)],recent=[(1),(6)]，此时的最大总和为 14。当 t=3，你游玩了第三首曲目，获得的单曲得分为 2，此时 total=[1,(6),(2)],recent=[1,(6),(2)]，此时的最大总和为 16。。当 t=4，你游玩了第四首曲目，获得的单曲得分为 3，此时total=[1,(6),2,(3)],recent=[(6),2,(3)]，此时的最大总和为 18。当 t=5，你游玩了第五首曲目，获得的单曲得分为 3，此时 total=[1,(6),2,(3),3],recent=[2,(3),(3)]，此时的最大总和为 15。由此可知，在时刻 4 计算出的最大总和最大，为 18。

解析：

s：模拟堆，记录最大的 b 个数据

sx：模拟堆，记录最后的 ra 个数中，最大的 rb 个数据

sy：最后的 ra 个数据中不存在 sx 中的数据

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<long long, long long> PLL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
const int INF = 0x3f3f3f3f;
const LL Mod = 1e9 + 7;
const int N = 2e5 + 10, M = 4e5 + 10, P = 110;
int n, b, ra, rb;
int ar[N];
multiset<PII>s,sx;
multiset<PII,greater<PII>>sy;int main() {cin >> n >> b >> ra >> rb;for (int i = 1; i <= n; i++) {scanf("%d", &ar[i]);}LL sum1 = 0, sum2 = 0;LL ans = 0;for (int i = 1; i <= n; i++) {s.insert({ ar[i],i });sum1 += ar[i];if (s.size() > b) {auto t = *s.begin();s.erase(t);sum1 -= t.first;}if (i > ra) {int j = i - ra;if (sx.count({ ar[j],j })) {sx.erase({ ar[j],j });sum2 -= ar[j];}else if (sy.count({ ar[j],j })) {sy.erase({ ar[j],j });}}if (sx.size() && ar[i] >= sx.begin()->first) {sx.insert({ ar[i], i });sum2 += ar[i];}else {sy.insert({ ar[i],i });}if (sx.size() < rb && sy.size()) {auto t = *sy.begin();sy.erase(t);sx.insert(t);sum2 += t.first;}if (sx.size() > rb) {auto t = *sx.begin();sx.erase(t);sy.insert(t);sum2 -= t.first;}ans = max(ans,sum1 + sum2);}cout << ans << endl;return 0;
}

这篇关于D 无限的韵律源点 (STL_set ,*****)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---