代码编织梦想

F - Apples

F

题意

N N N 个苹果,每个苹果会在 T i T_i Ti 的时刻落到 X i X_i Xi 的位置。现在要求使用一个长度为 W W W、使用时间耐久度为 D D D 的篮子装这些苹果,问最多能装多少苹果

思路

不妨以位置 x x x 轴,时间 y y y 轴,建立二维直角坐标系。那么每个苹果 ( X i , T i ) (X_i,T_i) (Xi,Ti) 就可以抽象成二维平面上的一个点。篮子可以抽象成一个长为 W W W,高为 D D D 的一个矩形。那么问题就转化为了怎样选择这个矩形,使得能包含的点最多?

如下图,我们用矩形的右上顶点来表示每一个矩形,那么对于一个苹果点 ( X i , T i ) (X_i,T_i) (Xi,Ti),能够包含这个点的篮子右上顶点的区域就是下图矩形表示的区域。
1

显然每一个点都对应唯一的一个矩形区域, 那么所有的这些矩形区域的重合最多的地方,就是最佳的放置篮子右上顶点的位置(类似下图中红色的位置)。

2

到了这里就可以用扫描线来解决了。使用一条水平线,从下到上扫描,遇到一个矩形的下边就把对应的 [ X i , X i + W − 1 ] [X_i,X_i+W-1] [Xi,Xi+W1] 这段区间 + 1 +1 +1,遇到上边 − 1 -1 1
只需要在从下到上扫描的过程中维护一下答案最大值即可。

3

// Problem: F - Apples
// Contest: AtCoder - HHKB Programming Contest 2023(AtCoder Beginner Contest 327)
// URL: https://atcoder.jp/contests/abc327/tasks/abc327_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n' 
#define ull unsigned long long

const int INF=0x3f3f3f3f;
const long long INFLL=0x3f3f3f3f3f3f3f3fLL;

typedef long long ll;

const int N=200050;

struct Point{
	int x;
	int y;
	int delta;
	Point(int x=0,int y=0,int delta=0):x(x),y(y),delta(delta){}
	bool operator < (const Point& pt) const{
		return y < pt.y || (y == pt.y && delta > pt.delta); //优先区间+
	}
};

Point p[N<<1];
int size; //size = n*2

struct node{
	int lazy;
	int maxv;
}tree[1<<21];

void build(int p,int l,int r){
	tree[p] = {0,0};
	if(l == r){
		return;
	}
	int mid = l+r>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}

void push_down(int p){
	tree[p<<1].maxv += tree[p].lazy;
	tree[p<<1].lazy += tree[p].lazy;
	tree[p<<1|1].maxv += tree[p].lazy;
	tree[p<<1|1].lazy += tree[p].lazy;
	tree[p].lazy = 0;
}

void update(int p,int l,int r,int L,int R,int d){ //[L,R] += d
	if(L <= l && r <= R){
		tree[p].maxv += d;
		tree[p].lazy += d;
		return;
	}
	if(tree[p].lazy)	push_down(p);
	int mid = l+r>>1;
	if(L <= mid)	update(p<<1,l,mid,L,R,d);
	if(R > mid)	update(p<<1|1,mid+1,r,L,R,d);
	tree[p].maxv = std::max(tree[p<<1].maxv,tree[p<<1|1].maxv);
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int n,D,W;
    std::cin>>n>>D>>W;
    int up = 0;
    fore(i,1,n+1){
    	int T,X;
    	std::cin>>T>>X;
    	p[++size] = Point(X,T,1); //矩形下边
    	p[++size] = Point(X,T+D-1,-1); //矩形上边
    	up = std::max(up,X+W-1);  //最大X坐标
    }
    std::sort(p+1,p+1+size); //按y值排序
    build(1,1,up);
    int ans = 0;
    fore(i,1,size+1){
    	update(1,1,up,p[i].x,p[i].x+W-1,p[i].delta);
    	ans = std::max(ans,tree[1].maxv); //某个被重合最多的点
    }
    std::cout<<ans;
	return 0; 
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/m0_73500785/article/details/134248887

c++中string的库函数-爱代码爱编程

山再高,往上攀,总能登顶! 路再长,走下去,定能到达! 🎥烟雨长虹,孤鹜齐飞的个人主页 🔥个人专栏c++ 期待小伙伴们的支持与关注!!! 目录 前言: string的简介 ​编辑 string的组成 string的功能  string的基本用法  string的声明与初始化

虚析构函数(c++)-爱代码爱编程

4.3 虚析构函数 4.3 虚析构函数 C++允许将析构函数定义为虚函数,为什么? #include <iostream> using namespace std; cla

使用 cmake 和 ninja 构建 c/c++ 项目的教程-爱代码爱编程

使用 CMake 和 Ninja 构建 C/C++ 项目的教程 CMake 是一个跨平台的开源构建工具,它简化了项目的构建过程。而 Ninja 是一个快速、轻量级的构建系统,与 CMake 配合使用可以提高项目的构建效率。

【c++】内存对齐-爱代码爱编程

本篇文章介绍C++中的内存对齐,后续介绍C的union和C++的variant的时候,需要用到这部分的知识。 占用内存 先回忆下C++各个数据类型占用的内存大小: int:所占内存大小:4byte = 32bit;ch

ue5 c++(十五)— timerhandle(定时器)的使用-爱代码爱编程

文章目录 设置定时器声明FTimerHandle定义执行函数设置定时器 清除定时器 定时器(Timer) 可用于执行延迟类型的操作,或让某些操作在一段时间内重复执行。 设置定时器 定

12. c++ kmalloc、kzalloc、vmalloc的区别-爱代码爱编程

kmalloc、kzalloc、vmalloc的区别 我们都知道在用户空间动态申请内存用的函数是 malloc(),这个函数在各种操作系统上的使用是一致的,对应的用户空间内存释放函数是 free()。注意:动态申请的内存使