题解：洛谷 P1672 [USACO05FEB] Feed Accounting S

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1672 [USACO05FEB] Feed Accounting S - 洛谷【题目描述】约翰想知道上一船饲料是什么时候运到的。在饲料运到之前他的牛正好把仓库里原来的饲料全吃光了。他收到运来的F 1 ( 1 ≤ F 1 ≤ 10 6 ) F1(1\le F1\le 10^6)F1(1≤F1≤106)千克饲料。遗憾的是他已经不记得这是哪一天的事情了。到第D ( 1 ≤ D ≤ 2 × 10 3 ) D(1\le D\le 2\times 10^3)D(1≤D≤2×103)天为止仓库里还剩下F 2 ( 1 ≤ F 2 ≤ F 1 ) F2(1\le F2\le F1)F2(1≤F2≤F1)千克饲料。约翰养了C ( 1 ≤ C ≤ 100 ) C(1\le C\le 100)C(1≤C≤100)头牛每头牛每天都吃掉恰好1 11千克饲料。由于不同的原因牛们从某一天开始在仓库吃饲料又在某一天离开仓库所以不同的两天可能会有差距很大的饲料消耗量。每头牛在来的那天和离开的那天都在仓库吃饲料。给出今天的日期D DD写一个程序判断饲料最近一次运到是在什么时候。今天牛们已经吃过饲料了并且饲料运到的那天牛们还没有吃过饲料。如果最终的答案有多个可能请输出最大的即最近的那一个。【输入】第1 11行四个整数C CCF 1 F1F1F 2 F2F2D DD用空格隔开。第2 22到C 1 C1C1行每行是用空格隔开的两个数字分别表示一头牛来仓库吃饲料的时间和离开的时间。【输出】一个正整数即上一船饲料运到的时间。【输入样例】3 14 4 10 1 9 5 8 8 12【输出样例】6【核心思想】问题分析给定C CC头牛在仓库的进食时间段、初始饲料量F 1 F1F1、第D DD天剩余量F 2 F2F2求饲料最近一次运到的日期。运到当天牛尚未进食之后每天牛按时间段吃饲料。这是一个差分数组 前缀和 逆向扫描问题关键在于用差分统计每天的牛数量从后往前累加找到恰好消耗F 1 − F 2 F1 - F2F1−F2饲料的那一天。算法选择差分数组将每头牛的进食区间[ l , r ] [l, r][l,r]转化为a [ l ] 1 a[l] \mathrel{} 1a[l]1、a [ r 1 ] − 1 a[r1] \mathrel{-} 1a[r1]−1实现O ( 1 ) O(1)O(1)区间标记前缀和还原b [ i ] b [ i − 1 ] a [ i ] b[i] b[i-1] a[i]b[i]b[i−1]a[i]得到每天实际在仓库吃饲料的牛数量逆向扫描从第D DD天往前累加每天的消耗量b [ i ] b[i]b[i]找到累计消耗等于F 1 − F 2 F1 - F2F1−F2的那天即为答案关键步骤读取输入C , F 1 , F 2 , D C, F1, F2, DC,F1,F2,D和C CC条牛的区间[ l i , r i ] [l_i, r_i][li​,ri​]差分标记对于每头牛a [ l i ] 1 a[l_i] \mathrel{} 1a[li​]1a [ r i 1 ] − 1 a[r_i 1] \mathrel{-} 1a[ri​1]−1前缀和还原b [ i ] b [ i − 1 ] a [ i ] b[i] b[i-1] a[i]b[i]b[i−1]a[i]i ii从1 11到D DDb [ i ] b[i]b[i]表示第i ii天吃饲料的牛数逆向扫描i ii从D DD递减到1 11s u m b [ i ] sum \mathrel{} b[i]sumb[i]累加从第i ii天到第D DD天的总消耗若s u m F 1 − F 2 sum F1 - F2sumF1−F2输出i ii并结束要求最近日期逆向首个满足条件的即为最大i ii时间/空间复杂度时间复杂度O ( C D ) O(C D)O(CD)差分标记O ( C ) O(C)O(C)前缀和 逆向扫描O ( D ) O(D)O(D)空间复杂度O ( D ) O(D)O(D)差分数组和前缀和数组差分数组与前缀和的核心思想区间操作降维差分数组将C CC个区间加法转化为2 C 2C2C个单点更新前缀和一次性还原每日实际值逆向贪心从后往前扫描保证找到的是最近的运到日期最大的满足条件的i ii总量守恒F 1 − F 2 F1 - F2F1−F2即为从运到日到第D DD天的总消耗量逆向累加找到恰好匹配点适用于区间覆盖统计 逆向查找匹配点类问题核心是差分高效处理区间和逆向扫描定位答案【解题思路】【算法标签】#普及 #差分【代码详解】#includebits/stdc.husingnamespacestd;// 定义常量constintN2005;// 最大天数范围// 变量定义intc;// 喂养记录的条数intf1;// 第一天之前FJ喂养的数量intf2;// 第d天之后FJ喂养的数量intd;// 总天数inta[N];// 差分数组intb[N];// 前缀和数组表示每天Bessie喂养的次数intmain(){// 输入数据cincf1f2d;// 处理每条喂养记录for(inti1;ic;i){intl,r;// 每条记录的起始天和结束天cinlr;// 使用差分数组// 在l天开始增加一次喂养a[l];// 在r1天减少一次喂养a[r1]--;}// 计算前缀和得到每天Bessie喂养的次数for(inti1;id;i){b[i]b[i-1]a[i];}// 从第d天往前计算intsum0;// 从第i天到第d天的总喂养次数for(intid;i1;i--){sumb[i];// 累加第i天的喂养次数// 检查条件f1 - sum f2// 即sum f1 - f2if(sumf1-f2){coutiendl;// 输出结果break;}}return0;}【运行结果】3 14 4 10 1 9 5 8 8 12 6