洛谷 P3462 [POI2007]ODW-Weights

题面：

先打了个贪心。直接所有容器从大到小排序，按这个顺序处理容器，每个容器每次装能够装进且最大的砝码。用multiset维护。

WA了（貌似洛谷还骗到40分？）

然后想了想改了一下。先二分答案，对于每个二分出的答案x显然最好方案是取最小的x个砝码。然后就当做只有这些砝码，用前面的贪心判是否能够取完这些砝码。

错误记录：没有对砝码按重量排序...

A掉了？（n*log^2而且常数大，因此bzojA不掉，其他两个地方可以A）而且貌似容器不排序（甚至random_shuffle）都没有关系？

不太会证..

 #pragma GCC optimize("Ofast")

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 #include<set>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,m;

 int a[],b[];

 multiset<int> s;

 bool judge(int x)

 {

     s.clear();

     int i,t;multiset<int>::iterator i1;

     for(i=;i<=x;++i)

         s.insert(b[i]);

     for(i=n;i>=;--i)

     {

         t=a[i];

         while(!s.empty()&&((i1=s.upper_bound(t))!=s.begin()))

         {

             --i1;

             t-=*i1;

             s.erase(i1);

         }

     }

     return s.empty();

 }

 int main()

 {

     int i;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;++i)

         scanf("%d",&a[i]);

     sort(a+,a+n+);

     for(i=;i<=m;++i)

         scanf("%d",&b[i]);

     sort(b+,b+m+);

     int l=,r=m,mid;

     while(l!=r)

     {

         mid=l+((r-l)>>);

         if(judge(mid+))    l=mid+;

         else    r=mid;

     }

     printf("%d",l);

     return ;

 }

网上有高妙的一个log做法

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 int n,m;

 int a[],b[],c[];

 int d[];

 int ans;

 void try_work(int p)

 {

     if(p>c[])    return;

     if(d[p]>=)

     {

         --d[p];

         d[p-]+=c[p]/c[p-];

     }

     else

     {

         try_work(p+);

         if(d[p]>=)

         {

             --d[p];

             d[p-]+=c[p]/c[p-];

         }

     }

 }

 int main()

 {

     int i,j;

     scanf("%d%d",&n,&m);

     for(i=;i<=n;++i)

         scanf("%d",&a[i]);

     for(i=;i<=m;++i)

         scanf("%d",&b[i]);

     sort(b+,b+m+);

     for(i=;i<=m;++i)

         c[++c[]]=b[i];

     c[]=unique(c+,c+c[]+)-c-;

     for(i=;i<=n;++i)

         for(j=c[];j>=;--j)

         {

             d[j]+=a[i]/c[j];

             a[i]%=c[j];

         }

     for(i=,j=;i<=m;++i)

     {

         while(c[j]<b[i])    ++j;

         if(d[j]>=)

         {

             --d[j];

             ++ans;

         }

         else

         {

             try_work(j+);

             if(d[j]>=)

             {

                 --d[j];

                 ++ans;

             }

         }

     }

     printf("%d",ans);

     return ;

 }

巴特西

洛谷 P3462 [POI2007]ODW-Weights

最新文章

热门文章