题解：AtCoder AT_awc0026_d Repainted Wall

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】AtCoderD - Repainted Wall【题目描述】Takahashi is painting a long horizontal wall with paint.高桥正在用油漆粉刷一堵长长的水平墙壁。The wall extends across the entire number line, and initially, every point on the number line has been painted0 00times. Takahashi performedN NNpainting operations. In thei ii-th operation( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N), he painted the interval[ L i , R i ] [L_i, R_i][Li​,Ri​](whereL i R i L_i R_iLi​Ri​) once. That is, for every point corresponding to a real numberx xxsatisfyingL i ≤ x ≤ R i L_i \leq x \leq R_iLi​≤x≤Ri​, the number of times it has been painted increased by1 11.这面墙覆盖了整个数轴初始时数轴上的每个点都被粉刷了0 00次。高桥进行了N NN次粉刷操作。在第i ii次操作1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N中他粉刷了区间[ L i , R i ] [L_i, R_i][Li​,Ri​]其中L i R i L_i R_iLi​Ri​一次。也就是说对于每个满足L i ≤ x ≤ R i L_i \leq x \leq R_iLi​≤x≤Ri​的实数x xx对应的点其被粉刷的次数增加了1 11。Parts that have been paintedK KKor more times are considered sufficiently thick and pass inspection, while parts painted fewer thanK KKtimes are too thin and fail.被粉刷K KK次或更多次的区域被认为是足够厚的并通过检查而被粉刷少于K KK次的区域则太薄而未通过。After all operations are completed, find thetotal lengthof the set of all points that have been paintedK KKor more times (that is, the sum of the lengths of each interval that constitutes this set).在所有操作完成后求被粉刷K KK次或更多次的所有点组成的集合的总长度即构成该集合的每个区间长度之和。For example, if the set of all points paintedK KKor more times is the union of intervals[ 1 , 5 ] [1, 5][1,5]and[ 7 , 9 ] [7, 9][7,9], the answer is( 5 − 1 ) ( 9 − 7 ) 6 (5 - 1) (9 - 7) 6(5−1)(9−7)6.例如如果被粉刷K KK次或更多次的所有点组成的集合是区间[ 1 , 5 ] [1, 5][1,5]和[ 7 , 9 ] [7, 9][7,9]的并集则答案为( 5 − 1 ) ( 9 − 7 ) 6 (5 - 1) (9 - 7) 6(5−1)(9−7)6。Note that since allL i L_iLi​andR i R_iRi​are integers, the boundaries where the paint count changes occur only at integer coordinates. Therefore, the answer is always an integer.注意由于所有L i L_iLi​和R i R_iRi​都是整数油漆次数变化的边界仅出现在整数坐标处。因此答案总是一个整数。【输入】N NNK KKL 1 L_1L1​R 1 R_1R1​L 2 L_2L2​R 2 R_2R2​⋮ \vdots⋮L N L_NLN​R N R_NRN​The first line contains an integerN NNrepresenting the number of painting operations and an integerK KKrepresenting the threshold number of coats required to pass inspection, separated by a space.Thei ii-th of the followingN NNlines( 1 ≤ i ≤ N ) (1 \leq i \leq N)(1≤i≤N)contains the left endpointL i L_iLi​and right endpointR i R_iRi​of the interval painted in thei ii-th operation, separated by a space.【输出】Output the total length of the set of all points paintedK KKor more times, as an integer on a single line.【输入样例】3 2 1 5 3 7 6 9【输出样例】3【解题思路】【算法标签】#贪心#【代码详解】#includebits/stdc.husingnamespacestd;constintN200005;intn,k,ans,cnt;// n: 区间数量k: 阈值ans: 总长度cnt: 当前覆盖次数mapint,intmp;// 差分映射key为坐标value为变化量intmain(){cinnk;// 读入区间数量和阈值for(inti1;in;i)// 处理每个区间{intl,r;cinlr;// 读入区间左端点和右端点mp[l];// 在l处进入区间覆盖次数1mp[r]--;// 在r处离开区间覆盖次数-1}intlast0,cnt0;// last: 上一个坐标点cnt: 当前覆盖次数// 扫描线遍历所有关键点for(autox:mp)// 按坐标从小到大遍历{intposx.first;// 当前坐标intdeltax.second;// 覆盖次数的变化量if(cntk)// 如果上一个区间的覆盖次数≥k{// 累加上一个区间[last, pos)的长度anspos-last;}lastpos;// 更新上一个坐标cntdelta;// 更新当前覆盖次数}coutansendl;// 输出总长度return0;}【运行结果】3 2 1 5 3 7 6 9 3