P1672 [USACO05FEB] Feed Accounting S 题解

题目链接

思路

一道特别简单的差分模板题，其实也有点推理的感觉。

对于每头牛，我们通过两次循环使用差分倒推出在这几天内它对我们饲料消耗的贡献，进而推出每一天的饲料消耗量，从 \(D\) 天到现在一共吃掉的饲料数为 \(F1-F2\) 的那一天即是我们所求的。

输入的时候依照题意模拟一次差分，扫一遍差分，算出每一天的饲料消耗量，再扫一遍每天饲料消耗量，用一个变量储存在算出从 \(D\) 天到现在一共吃掉的饲料数，推出上一船饲料运到的时间。时间复杂度为 \(O(c+2d)\)。

参考代码（请勿抄袭）：

#include<bits/stdc++.h>
using namespace std;
int c,f1,f2,d,begi,en,b[20005],sum[20005],s;//b为差分数组，sum为每天的消耗量数组，s为这一天的饲料总和

int main(){
    scanf("%d%d%d%d",&c,&f1,&f2,&d);//输入牛的数量，运来的饲料量，剩下的饲料量
    for(int i=1;i<=c;i++){
        scanf("%d%d",&begi,&en);//输入每头牛来和走的时间
        b[begi]++;
        b[en+1]--;//差分
    }
    for(int i=1;i<=d;i++) sum[i]=sum[i-1]+b[i];//算出每天饲料消耗量
    for(int i=d;i>=1;i--){//从现在往以前倒推
        s+=sum[i];//算出从D天到现在一共吃掉了多少饲料
        if(s==f1-f2){//找到了满足条件的那一天
            printf("%d",i);//输出结果
            exit(0);//结束程序
        }
    }
    return 0;
}