题解：AtCoder AT_awc0098_b Library Book Lending

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderB - Library Book Lending【题目描述】Takahashi works part-time at a university library. At this library, the books a student can borrow are restricted based on their study level.There areN NNstudents registered at the library, numbered from1 11toN NN. The study level of studenti iiis an integerS i S_iSi​.The library hasM MMbooks, numbered from1 11toM MM. The minimum study level required to borrow bookj jjis an integerT j T_jTj​.Studenti iican borrow bookj jjif and only ifS i ≥ T j S_i \geq T_jSi​≥Tj​.Note that the same book can be borrowed by multiple students independently. That is, the number of books a student can borrow is not affected by the borrowing status of other students.For each of theN NNstudents, determine the number of books that student can borrow. Specifically, for eachi ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N), find the countC i C_iCi​of booksj jj( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)satisfyingS i ≥ T j S_i \geq T_jSi​≥Tj​.高橋在一所大学图书馆做兼职。在这家图书馆学生可以借阅的书籍受到其学习水平的限制。图书馆有N NN名注册学生编号从1 11到N NN。学生i ii的学习水平为整数S i S_iSi​。图书馆有M MM本书编号从1 11到M MM。借阅第j jj本书所需的最低学习水平为整数T j T_jTj​。当且仅当S i ≥ T j S_i \geq T_jSi​≥Tj​时学生i ii可以借阅第j jj本书。注意同一本书可以被多名学生独立借阅。也就是说一名学生可以借阅的书籍数量不受其他学生借阅情况的影响。对于每名N NN名学生确定该学生可以借阅的书籍数量。具体地对于每个i ii( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)求满足S i ≥ T j S_i \geq T_jSi​≥Tj​的书籍j jj( 1 ≤ j ≤ M ) (1 \leq j \leq M)(1≤j≤M)的数量C i C_iCi​。【输入】N NNM MMS 1 S_1S1​S 2 S_2S2​… \ldots…S N S_NSN​T 1 T_1T1​T 2 T_2T2​… \ldots…T M T_MTM​The first line contains the number of studentsN NNand the number of booksM MM, separated by a space.The second line contains the study levels of each studentS 1 , S 2 , … , S N S_1, S_2, \ldots, S_NS1​,S2​,…,SN​, separated by spaces.The third line contains the minimum study levels required to borrow each bookT 1 , T 2 , … , T M T_1, T_2, \ldots, T_MT1​,T2​,…,TM​, separated by spaces.【输出】C 1 C_1C1​C 2 C_2C2​⋮ \vdots⋮C N C_NCN​OutputN NNlines. Thei ii-th line( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)should containC i C_iCi​, the number of books that studenti iican borrow.【输入样例】3 4 2 1 3 1 2 3 2【输出样例】3 1 4【算法标签】#整数二分【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;// 最大学生/书籍数量intn,m;// n: 学生数量, m: 书籍数量ints[N],t[N];// s[i]: 学生i的学习水平, t[j]: 书籍j的最低学习水平要求intmain(){cinnm;// 读入学生数量和书籍数量// 读入每个学生的学习水平for(inti1;in;i)cins[i];// 读入每本书的最低学习水平要求for(inti1;im;i)cint[i];// 对书籍的最低学习水平要求数组排序升序// 排序后可以用二分查找快速统计满足条件的书籍数量sort(t1,tm1);// 对每个学生二分查找可以借阅的书籍数量for(inti1;in;i){// upper_bound(t1, tm1, s[i]) 返回第一个大于 s[i] 的位置// 减去 t 得到该位置的下标从1开始计数// 再减1得到最后一个小于等于 s[i] 的位置// 即满足 t[j] s[i] 的书籍数量intposupper_bound(t1,tm1,s[i])-t-1;coutposendl;// 输出学生i可以借阅的书籍数量}return0;}【运行结果】3 4 2 1 3 1 2 3 2 3 1 4