BZOJ 1110 POI 2007分銅Odw貪欲
与えられたn個の分銅とm個のリュックサックは、任意の二つの分銅に対してもう一つの正の整数倍があることを保証します.
http://hzwer.com/4761.html
たぶん仕分けを考えましたが、具体的にはどうすればいいですか?
私はまだ弱すぎます.
http://hzwer.com/4761.html
たぶん仕分けを考えましたが、具体的にはどうすればいいですか?
私はまだ弱すぎます.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 100100
using namespace std;
int n,m,ans;
int a[M],b[M];
int stack[40],top;
long long digit[40];
int main()
{
int i,j,k;
cin>>n>>m;
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=m;i++)
scanf("%d",&b[i]);
sort(b+1,b+m+1);
for(i=1;i<=m;i++)
if(i==1||b[i]!=b[i-1])
stack[++top]=b[i];
for(i=1;i<=n;i++)
for(j=top;j;j--)
digit[j]+=a[i]/stack[j],a[i]%=stack[j];
for(j=1,i=1;i<=top;i++)
for(;j<=m&&b[j]==stack[i];j++)
{
if(digit[i])
{
++ans;--digit[i];
continue;
}
for(k=i+1;k<=top;k++)
if(digit[k])
break;
if(k==top+1)
{
cout<<ans<<endl;
return 0;
}
for(;k>i;k--)
digit[k]--,digit[k-1]+=stack[k]/stack[k-1];
++ans;--digit[i];
}
cout<<ans<<endl;
return 0;
}