首页 > 其他分享 >ARC147E 做题记录

ARC147E 做题记录

时间:2024-07-05 19:09:59浏览次数:16  
标签:le cntb 记录 ll pb maxn ARC147E define

link

巧妙的题。

我们相当于选择一个尽量小的集合 \(S\),重新分配 \(S\) 中所有人的分数,使得最后所有人都满足要求。

先把本来就不符合要求的加入 \(S\),然后考虑再多加哪些人。

考虑转化条件:考虑从值域入手。发现 \(S\) 合法的充要条件是:\(\forall k\),\(\sum\limits_{x \in S} [a_x \le k] \ge \sum\limits_{x \in S} [b_x \le k]\)。

证明比较显然。

那么我们可以离散化,然后从小到大枚举值域。维护 \(a_x\le k\) 和 \(b_x\le k\) 的人的个数 \(cnta,cntb\),用大根堆维护可以其他的可以贡献的人即可。

这启示我们,条件的转化不一定需要性质,换个入手点也一样行。

点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define pir pair <ll, ll>
#define fi first
#define se second
#define mkp make_pair
using namespace std;
const ll maxn = 6e5 + 10;
ll n, a[maxn], b[maxn], h[maxn], ht, cnta, cntb, dr[maxn], tr[maxn];
vector <ll> vec[maxn], vect[maxn];
priority_queue <pir> q;
int main() {
	scanf("%lld", &n);
	for(ll i = 1; i <= n; i++) {
		scanf("%lld%lld", a + i, b + i);
		h[++ht] = a[i], h[++ht] = b[i];
	}
	sort(h + 1, h + 1 + ht);
	ht = unique(h + 1, h + 1 + ht) - h - 1;
	for(ll i = 1; i <= n; i++) {
		a[i] = lower_bound(h + 1, h + 1 + ht, a[i]) - h;
		b[i] = lower_bound(h + 1, h + 1 + ht, b[i]) - h;
		if(a[i] >= b[i]) vec[b[i]].pb(i);
		else vect[a[i]].pb(i);
	}
	for(ll i = 1; i <= ht; i++) {
		for(ll j: vect[i]){
			++dr[b[j]];
			++cnta;
		}
		for(ll j: vec[i]) q.push(mkp(a[j], j));
		cntb += dr[i], cnta += tr[i];
		while(cnta > cntb) {
			ll x = q.empty()? 0 : q.top().se;
			if(a[x] <= i) {
				puts("-1");
				return 0;
			}
			++cntb, q.pop();
			++tr[a[x]];
		}
	}
	printf("%lld", (ll) q.size());
	return 0;
}

标签:le,cntb,记录,ll,pb,maxn,ARC147E,define
From: https://www.cnblogs.com/Sktn0089/p/18286449

相关文章

  • C++基础知识持续更新,今天来记录结构体的基本知识,包括结构体的定义和使用,结构体数组,结
    C++结构体C++基础知识持续更新,今天来记录结构体的基本知识,包括结构体的定义和使用,结构体数组,结构体指针,结构体嵌套结构体,结构体做函数参数,结构体中的const的使用场景,以及结构体的案例。1.结构体的定义和使用结构体属于用户自定义的数据类型,允许用户存储不同的数据类型。......
  • MinIO使用记录
    探索MinIO:高性能、分布式对象存储解决方案注:本文除代码外多数为AI生成最近因为有项目需要换成AmazonS3的云存储,所以把之前做过的minio部分做一个记录,后面也会把基于这版改造的S3方法发出来记录。MinIO简介MinIO是一款高性能、分布式对象存储服务器,设计用于在大规模环境中......
  • 详解Web应用安全系列(8)不足的日志记录和监控
    在Web安全领域,不足的日志记录和监控是一个重要的安全隐患,它可能导致攻击者能够更隐蔽地进行攻击,同时增加了攻击被检测和响应的难度。以下是对Web攻击中不足的日志记录和监控漏洞的详细介绍。一、日志记录不足的问题日志缺失或不完整关键操作未记录:如用户登录、敏感数据......
  • 程序人生日记20240705|工作零食:米饭+十分米莲藕汁+饼干(减脂记录)
    程序员的工作饮食减脂记录打卡餐别:早餐零食详情:(同事给的不算统计内)零食名称:十分米莲藕汁1杯主食选择:全麦法棍。大致热量估算:莲藕汁约50卡,低脂法棍约100卡,总计约150卡。初始数据:体重:90公斤目标:80公斤完成情况:完成。程序员自律宣言:程序猿不可以土肥圆~零食库剩余情况:10......
  • Bug记录|vivia主题|Hexo+GitHub搭建个人博客
    1.将本地SSH添加到远程github 中,之后关联远程或push出现以下错误:fatal:Notagitrepository(oranyoftheparentdirectories):.git解决方案:执行 gitinit。gitinit2.hexog无法成功运行,出现以下错误:TypeError:C:\Users\Maxence\Desktop\项目\MyBlog\Hexo......
  • lxl 又来讲课的记录
    太困难。P7124前置知识:Eden的新背包问题。这个题做法比较离谱。题意是求子树补不删除莫队。要求操作次数\(O(n\logn)\)。考虑类似于线段树分治的结构,如果递归左儿子,就加入右节点信息;如果递归右儿子,就加入左儿子信息。这样我们能在\(O(n\logn)\)次操作种算出每个叶子在序......
  • SQL 统计各个部门的工资记录数
    系列文章目录文章目录系列文章目录前言前言前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看懂了就去分享给你的码吧。描述有一个部门表departments简况如下:有一个,部门员工关系表dept_emp......
  • 记录--淘宝、京东复制好友链接弹出商品详情是如何实现的
    ......
  • 记录一下使用小程序反编译获取源码
    起因是自己开发的小程序源码被扒了,泄露了一些数据,要做优化调整代码,所以尝试扒自己开发的小程序源码。安装node.jswxappUnpacker(逆向反编译工具)使用夜神模拟器(直接是root默认,手机需要进入root模式,就是模拟器比较卡)实操流程如下打开wxappUnpacker所在文件夹,cmd进入命令......
  • LeetCode-刷题记录-滑动窗口合集(本篇blog会持续更新哦~)
    一、滑动窗口概述滑动窗口(SlidingWindow)是一种用于解决数组(或字符串)中子数组(或子串)问题的有效算法。SlidingWindow核心思想:滑动窗口技术的基本思想是维护一个窗口(一般是一个子数组或子串),该窗口在数组上滑动,并在滑动过程中更新窗口的内容。通过滑动窗口,可以在(O(......