题解：AtCoder AT_awc0020_e Shelving Books on a Bookshelf

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

AtCoder：E - Shelving Books on a Bookshelf

【题目描述】

Takahashi, working as a librarian, has been assigned the task of shelvingN NNbooks onto a bookshelf.
高桥作为一名图书管理员，被分配了一项任务，要将N NN本书上架到一个书架上。

The bookshelf hasM MMempty spaces arranged in a row, numbered from left to right as space1 11, space2 22,… \ldots…, spaceM MM. Each spacej jjhas an integer valueC j C_jCj​representing its “weight capacity,” and each space can hold at most1 11book.
书架上有M MM个空位排成一行，从左到右编号为位置1 11, 位置2 22,… \ldots…, 位置M MM。每个位置j jj有一个整数值C j C_jCj​表示其"承重能力"，每个位置最多能放1 11本书。

The books are numbered from1 11toN NN, and booki iihas an integer valueW i W_iWi​representing its “weight.”
书籍编号从1 11到N NN，书i ii有一个整数值W i W_iWi​表示其"重量"。

Takahashi determines the placement for each book one at a time, in the order book1 11, book2 22,… \ldots…, bookN NN, using the following procedure:
高桥按照书籍1 11, 书籍2 22,… \ldots…, 书籍N NN的顺序，使用以下步骤逐一确定每本书的放置位置：

• Among the spaces that do not yet have a book placed on them, consider as candidates those whose weight capacity is at least the weight of the book (i.e.,C j ≥ W i C_j \geq W_iCj​≥Wi​).
  在尚未放置书籍的位置中，考虑那些承重能力不低于书籍重量的位置（即C j ≥ W i C_j \geq W_iCj​≥Wi​）作为候选位置。
• If there is at least one candidate, place the book on the candidate space with the smallest number. The space where a book is placed becomes occupied and can no longer be selected for subsequent books.
  如果至少有一个候选位置，则将这本书放在编号最小的候选位置上。被放置书籍的位置变为已占用，不能再为后续书籍所选。
• If there are no candidates, give up on shelving that book. A book that is given up on is not placed on the bookshelf and is never reconsidered.
  如果没有候选位置，则放弃上架这本书。被放弃的书籍不会被放置在书架上，且后续也不再被考虑。

After considering the placement for all books, determine the number of books that were successfully placed on the bookshelf.
在考虑了所有书籍的放置后，确定成功放置在书架上的书籍数量。

【输入】

N NNM MM
W 1 W_1W1​W 2 W_2W2​… \ldots…W N W_NWN​
C 1 C_1C1​C 2 C_2C2​… \ldots…C M C_MCM​

• The first line containsN NN, the number of books, andM MM, the number of spaces on the bookshelf, separated by a space.
• The second line contains the weights of each bookW 1 , W 2 , … , W N W_1, W_2, \ldots, W_NW1​,W2​,…,WN​, separated by spaces.
• The third line contains the weight capacities of each spaceC 1 , C 2 , … , C M C_1, C_2, \ldots, C_MC1​,C2​,…,CM​, separated by spaces.

【输出】

Print the number of books that were successfully placed on the bookshelf, on a single line.

【输入样例】

4 5 3 5 2 7 4 6 3 8 2

【输出样例】

4

【解题思路】

【算法标签】

#线段树#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=200005,INF=1e9;intn,m,cnt;// n: 任务数量，m: 机器数量，cnt: 可完成的任务数intw[N],c[N];// w[i]: 第i个任务所需容量，c[i]: 第i台机器的容量structNode{intl,r;// 区间左右端点intdt,mx;// dt: 懒标记，mx: 区间最大值}tr[N*4];// 线段树数组，开4倍空间// 从子节点更新父节点的信息voidpushup(intu){tr[u].mx=max(tr[u<<1].mx,tr[u<<1|1].mx);// 取左右子树的最大值}// 下传懒标记voidpushdown(intu){auto&root=tr[u],&l=tr[u<<1],&r=tr[u<<1|1];l.dt+=root.dt,l.mx+=root.dt;// 更新左子树r.dt+=root.dt,r.mx+=root.dt;// 更新右子树root.dt=0;// 清空当前节点的懒标记}// 构建线段树voidbuild(intu,intl,intr){if(l==r)// 叶节点{tr[u]={l,r,0,c[l]};// 初始懒标记为0，值为机器容量}else{tr[u]={l,r};intmid=l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);// 递归构建左右子树pushup(u);// 更新当前节点的值}}// 单点更新：将位置pos的值更新为dvoidupdate(intu,intpos,intd){if(tr[u].l==tr[u].r)// 找到叶节点{tr[u].mx=d;// 更新值return;}else{pushdown(u);// 下传懒标记intmid=tr[u].l+tr[u].r>>1;if(pos<=mid)// 在左子树{update(u<<1,pos,d);}if(pos>mid)// 在右子树{update(u<<1|1,pos,d);}pushup(u);// 更新当前节点的值}}// 区间查询：查询区间[l, r]的最大值intquery(intu,intl,intr){if(tr[u].l>=l&&tr[u].r<=r)// 当前节点完全包含在查询区间内{returntr[u].mx;}else{pushdown(u);// 下传懒标记intmid=tr[u].l+tr[u].r>>1;intres=-INF;// 初始化为负无穷if(l<=mid)// 与左子树有交集{res=query(u<<1,l,r);}if(r>mid)// 与右子树有交集{res=max(res,query(u<<1|1,l,r));// 取最大值}returnres;}}// 在区间[l, r]中查找第一个大于等于val的位置，找不到返回-1intfind(intu,intl,intr,intval){if(tr[u].mx<val)// 当前区间最大值小于val，不可能找到{return-1;}if(tr[u].l==tr[u].r)// 叶节点{returntr[u].l;// 返回位置}intmid=(tr[u].l+tr[u].r)>>1;intres=-1;if(l<=mid)// 先在左子树找{res=find(u<<1,l,r,val);}if(res==-1&&r>mid)// 左子树没找到，在右子树找{res=find(u<<1|1,l,r,val);}returnres;}intmain(){cin>>n>>m;// 读入任务数量和机器数量for(inti=1;i<=n;i++){cin>>w[i];// 读入每个任务所需容量}for(inti=1;i<=m;i++){cin>>c[i];// 读入每台机器的容量}build(1,1,m);// 构建线段树，管理机器容量for(inti=1;i<=n;i++)// 遍历每个任务{// 查找第一个容量大于等于w[i]的机器intpos=find(1,1,m,w[i]);if(pos!=-1)// 找到了合适的机器{cnt++;// 可完成的任务数加1update(1,pos,-INF);// 将该机器的容量设为负无穷，表示已使用}}cout<<cnt<<endl;// 输出可完成的任务数return0;}

【运行结果】

4 5 3 5 2 7 4 6 3 8 2 4