# [BZOJ1676]&&[Usaco2005 Feb]Feed Accounting 饲料计算

## 描述 Description

Farmer John is trying to figure out when his last shipment of feed arrived. Starting with an empty grain bin, he ordered and received F1 (1 <= F1 <= 1,000,000) kilograms of feed. Regrettably, he is not certain exactly when the feed arrived. Of the F1 kilograms, F2 (1 <= F2 <= F1) kilograms of feed remain on day D (1 <= D <= 2,000). He must determine the most recent day that his shipment could have arrived. Each of his C (1 <= C <= 100) cows eats exactly 1 kilogram of feed each day. For various reasons, cows arrive on a certain day and depart on another, so two days might have very different feed consumption. The input data tells which days each cow was present. Every cow ate feed from Farmer John’s bin on the day she arrived and also on the day she left. Given that today is day D, determine the minimum number of days that must have passed since his last shipment. The cows have already eaten today, and the shipment arrived before the cows had eaten.

## 输入格式 InputFormat

Line 1: Four space-separated integers: C, F1, F2, and D * Lines 2..C+1: Line i+1 contains two space-separated integers describing the presence of a cow. The first integer tells the first day the cow was on the farm; the second tells the final day of the cow’s presence. Each day is in the range 1..2,000.

## 输出格式 OutputFormat

The last day that the shipment might have arrived, an integer that will always be positive.

4 63 29 40
9 25
32 56
11 44
4 29

24

Silver

BZOJ 1676

## 代码 Code

``````#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf=0x7fffffff/11.27;
int i,j,t,n,m,l,r,k,z,y,x;
inline void read(int &x)
{
x=0;char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
}
int c,f1,f2,d;
int f;
int main()
{
memset(f,0,sizeof(f));
read(c);read(f1);read(f2);read(d);
for (i=1;i<=c;i++)
{
read(x);read(y);
if (x<=d) f[x]++;
if (y+1<=d) f[y+1]--;
}
for (i=1;i<=d;i++) f[i]=f[i]+f[i-1];
for (i=d;i>=1;i--)
{
f2+=f[i];
if (f2>=f1) break;
}
printf("%d\n",i);
return 0;
}``````