problem-solved's blog

By problem-solved, 12 years ago, In English
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int inf = ~0u>>2;
int c3,c4,c5,k3,k4,k5;
int F(){
	return abs(c3*k3-c4*k4)+abs(c4*k4-c5*k5);
}
int main()
{
	int n,s,i,j,k;
    scanf("%d%d",&n,&s);
	for(c3=c4=c5=0;n;n--)
	{
		scanf("%d",&j);
		if(j==3) c3++;
		if(j==4) c4++;
		if(j==5) c5++;
	}
	int ans=inf,x,y,z;
	for(k3=s/(c3+c4+c5);k3>=0;k3--)
	{
		int up=inf;
		for(k4=(s-k3*c3)/(c4+c5);k4>=k3;k4--)
		{
			k5=(s-c3*k3-k4*c4);if(k5%c5) continue;
			k5/=c5;
			if(k5<k4 ) continue;
			int tmp=F();
			if(tmp<up)
			{ 
				up=tmp;
				if(up<ans)
				{
					ans=up;
					x=k3;y=k4;z=k5;
				}
			}
			else break;//where is the monotonicity
                     //why can we use break here,I can't understand
		}
	}
	if(ans==inf) printf("-1\n");
	else printf("%d %d %d\n",x,y,z);
}
  • Vote: I like it
  • -18
  • Vote: I do not like it