(题目链接)

题意

　　一堆不知何时运到的草料原有F1 kg，在第D天被牛吃成F2 kg，每头牛在[l,r]吃草料，每天吃1kg。求草料是什么时候运到的。

Solution

　　原来这就是差分。。。将线段拆成点，权值为1（左端点）-1（右端点），那么离散端点后从左向右扫即可。

代码

// poj2459#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int C,F1,F2,D,a[1000010];int main() { int mx=0; scanf("%d%d%d%d",&C,&F1,&F2,&D); for (int u,v,i=1;i<=C;i++) { scanf("%d%d",&u,&v); a[v]++;a[u-1]--;mx=max(v,mx); } int sum=0; for (int i=D+1;i<=mx;i++) sum+=a[i]; for (int i=D;i>=0;i--) { sum+=a[i]; F2+=sum; if (F2==F1) {printf("%d",i);return 0;} } puts("0"); return 0;}