题目大意

简单翻译一下：给 \(c\) 个区间表示牛吃草的时间段，每头牛每天吃 \(1\) 千克，问距今天（即运来饲料 \(f_2\) 千克的时间）最近的送饲料 \(f_1\) 千克的时间是什么时候？

思路

初步思路

我们设 \(a_i\) 代表第 \(i\) 天吃了几千块的饲料，那么对于每头牛的吃饲料的时间，则需要将 \(a_l\) 到 \(a_r\) 均暴力 \(+1\)，然后从 \(d\) 往前遍历 \(x\)，若 \(\sum^{i=x}_{d}a_i=f_2-f_1\)，则第 \(x\) 天就是答案。

优化

这种暴力的复杂度显然不够优秀。

我们再来会看一下刚刚的暴力思路：

向将 \(a_l\) 到 \(a_r\) 均 \(+1\) 这样的区间修改，我们易想到用差分来优化，于是的 \(a\) 数组可用 \(O(D)\) 求得。

在求答案时，求的 \(\sum^{i=x}_{d}a_i\) 不难看出就是 \(a\) 数组的后缀和，那么易想到利用前缀和的思想 \(O(1)\) 求得解。

时间复杂度 \(O(C+D)\)

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e3+1;
int c,d,f1,f2;
int dif[N];//差分
int a[N];
int sum[N];//后缀和
int main(){
	cin>>c>>f1>>f2>>d;
	int f=f1-f2;
	for(int i=1;i<=c;i++){
		int l,r;
		cin>>l>>r;
		dif[l]++;
		dif[r+1]--;//差分进行区间修改
	}
	for(int i=1;i<=d;i++)a[i]=a[i-1]+dif[i];
	for(int i=d;i>=1;i--){
		sum[i]=sum[i+1]+a[i];
		if(sum[i]==f){
			cout<<i;
			break;
		}
	}
	return 0;
}