首页 > 其他分享 >ABC249F 题解

ABC249F 题解

时间:2023-04-15 09:45:12浏览次数:52  
标签:int 题解 sum text 操作 include ABC249F

前言

题目传送门!

更好的阅读体验?

很好玩的贪心。

思路

如果第 \(i\) 次操作为覆盖操作,那么 \(1 \sim i-1\) 次操作都是无效的,原因显然。

这启示我们从后往前扫(前面的会被忽略,后面的不会啊!)。

在此基础上,就是分类讨论一下(假设当前的最大答案为 \(sum\)):

  • 当前操作是覆盖操作:
    • 如果不删 \(a_i\),那么 \((sum + a_i)\) 就是最终答案,因为更前面的操作会被省略。
    • 如果删 \(a_i\),那么这次操作无效,但是能操作的次数少了。所以 \(k \gets k-1\),继续。
  • 当前操作时增加操作:
    • 如果 \(a_i \ge 0\),加了肯定时好的,所以直接 \(sum \gets sum + a_i\)。
    • 如果 \(a_i < 0\),加了肯定变差,所以我们试图不加它。但是当不加的数量超过 \(k\) 时,不得不把某些操作重新加上。

对于最后一项,我们可以把 \(sum\) 重新加上当前最大的元素。所以只需要一个优先队列,当 \(\text{size} > k\) 时就扔掉 \(\max\limits_{x \in \text{queue}} x\)。

当 \(k < 0\) 的时候就不能操作了,请直接退出程序。另外操作完全部后,\(sum\) 也是可以作为答案的,记得更新一下。

代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 2e5 + 5;
int op[N], a[N];
int main()
{
	priority_queue <int> q;
	int n, k;
	long long ans = -9e18, sum = 0;
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d%d", &op[i], &a[i]);
	for (int i = n; i && ~k; i--)
	{
		if (op[i] == 1) ans = max(ans, a[i] + sum), k--;
		else if (op[i] == 2)
		{
			if (a[i] >= 0) sum += a[i];
			else q.push(a[i]);
		}
		while ((int)q.size() > k) sum += q.top(), q.pop(); //把比较大的元素扔掉 
	}
	cout << max(ans, sum);
	return 0;
}

希望能帮助到大家!

标签:int,题解,sum,text,操作,include,ABC249F
From: https://www.cnblogs.com/liangbowen/p/17320550.html

相关文章

  • 【题解】Tree MST
    题面给定一棵\(n\)个节点的树,现有有一张完全图,两点\(x,y\)之间的边长为\(w_x+w_y+dis_{x,y}\),其中\(dis\)表示树上两点的距离。求完全图的最小生成树。\(n\leq2\times10^5\)。题解???神秘借鉴支配对的思想,点分治后将树中点权替换为\(dep_i+w_i\),选择点权最小的一个......
  • [ABC296Ex] Unite 题解
    考虑状压dp。设\(f_{i,j,s}\)表示当前正在决策坐标为\((i,j)\)的格子,且列状态为\(s\)。其中列状态维护了当前轮廓线上的连通块,我们可以使用最小表示法来简单维护。(为什么不用广义括号序列?因为其涉及到\(5\)个可选值,由于\(m\le7\),所以这两个都需要用到八进制,而最小表示......
  • [Educational Codeforces Round 118 (Rated for Div. 2)]题解
    A题意:给定两个数,每一个数有两个属性,第一个属性是p1,第二个属性是p2.表示这个数有p2个后缀0.这个数本身等于p1后面加p2个0.问给你两个这种数,判断大小。思路:赛场上想到的:如果最终的长度不一样,可以直接根据长度判断。如果相等,就把后缀0加上直接比较大小就可以(比较字典序的大小),但......
  • 2012-2013 ACM-ICPC, NEERC, Moscow Subregional Contest题解
    题目链接:2012-2013ACM-ICPC,NEERC,MoscowSubregionalContestC.Cinderella(贪心)思路答案为大于平均值的数的数量代码#include<bits/stdc++.h>usingnamespacestd;usingi64=longlong;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);......
  • CF1473D 题解
    题目传送门题目分析线段树、前缀和、\(\text{ST}\)表题解都有了,我补一发猫树题解吧。由于每次操作只能将大小改变成跟原来差\(1\),所以只需要知道这段操作中的最大值和最小值,最后所求的答案的范围就被卡住了。对于每一次操作,我们把操作序列拦腰斩断,那么分别求两边的范围,最后减......
  • CF1758D 题解
    前言题目传送门!更好的阅读体验?用一种非常麻烦的做法把自己写自闭了,和题解区不一样,但是方法困难很多。思路代码属于混乱邪恶了,凑合着看看。#include<iostream>#include<cstdio>#include<cmath>usingnamespacestd;intn,ans[300005];longlongcalc(){ longlo......
  • ubuntu 20.04 基于docker快速搭建中文 的一些问题解决 Utilization of discoverer pro
    1.Utilizationofdiscovererprocessesover75%解决办法问题状态如下zabbixserver在开启Discovery功能后,zabbixweb页面报警提示:“Zabbixserver:Ulitizationofdiscovererprocessesover75%”。原因:每个discovery任务占用一个discovery进程,但是zabbixserver默认只配置了一......
  • scikit-learn 中 Boston Housing 数据集问题解决方案
    scikit-learn中BostonHousing数据集问题解决方案在部分旧教程或教材中是sklearn,现在【2023】已经变更为scikit-learn作用:开源机器学习库,支持有监督和无监督学习。它还提供了用于模型拟合、数据预处理、模型选择、模型评估和许多其他实用程序的各种工具。安装pipinsta......
  • 题解:C Future
    题目:给n个范围,第i个范围选pi,然后定义特征值k=p1+p2+...+pn。这次的开心度就是A(k%m)。m是给的一个数组A,长度为m。 要求:  就是个全排列组合的问题,找规律。 举个例子,有n个礼物,分别是(L1,R1)(L2,R2)(Ln,Rn)每个区间取个数然后相加,所有出现的结果,其实就是A[L1+L2+........
  • [ARC127E] Priority Queue 题解
    首先我们每次加入的数必定是一个\(1\sima\)的排列,但从排列角度考虑的话非常复杂,因为\(s\)是一个集合。所以我们考虑最后能剩下哪些数。考虑最后剩下的集合为\(\{a_i\}\),其中\(a_i<a_{i+1}\),显然这个集合里面的元素个数为\(A-B\)。那么我们会发现一件事情:我们按上升序依......