P1510 精卫填海

P1510 精卫填海
二分答案
二分背包容量，判断能否满足v。
判断的话就跑01背包就好了。

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<algorithm>

 #include<cmath>

 #include<ctime>

 #include<set>

 #include<map>

 #include<stack>

 #include<cstring>

 #define inf 2147483647

 #define For(i,a,b) for(register int i=a;i<=b;i++)

 #define p(a) putchar(a)

 #define g() getchar()

 //by war

 //2017.10.28

 using namespace std;

 int f[];

 int v,n,c;

 int l,r,mid;

 int tov;

 int tow;

 struct stone

 {

     int v;

     int w;

 }a[];

 void in(int &x)

 {

     int y=;

     char c=g();x=;

     while(c<''||c>'')

     {

     if(c=='-')

     y=-;

     c=g();

     }

     while(c<=''&&c>='')x=x*+c-'',c=g();

     x*=y;

 }

 void o(int x)

 {

     if(x<)

     {

         p('-');

         x=-x;

     }

     if(x>)o(x/);

     p(x%+'');

 }

 bool pd(int ans)

 {

     For(i,,ans)

     f[i]=;

     For(i,,n)

       for(int j=ans;j>=a[i].w;j--)

         f[j]=max(f[j],f[j-a[i].w]+a[i].v);

     if(f[ans]>=v)

     return true;

     return false;

 }

 int main()

 {

     in(v),in(n),in(c);

     For(i,,n)

     {

         in(a[i].v),in(a[i].w);

         tov+=a[i].v;

     }

     if(tov<v)

     {

         puts("Impossible");

         exit();

     }

     l=,r=c;

     while(l<r)

     {

         mid=(l+r)>>;

         if(pd(mid))

         r=mid;

         else

         l=mid+;

     }

     if(!pd(l))

     {

         puts("Impossible");

         exit();

     }

     o(c-l);

      return ;

 }