Codeforces 110C Lucky Sum Of Digits 暴力_【c系列3.8】lucky sum of digits

点击打开链接

题意:求digit和为n(n<=1e6)&&只含有4,7的最小数字
假设最后有p个4,q个7 为了最小:4排在前面,7排在后面,求出4,7个数即可
4p+7q=n 枚举q,p=(n-7q)/4,数字尽量小->位数p+q尽量小,q尽量小即可. 

#include <bits/stdc++.h>
using namespace std;
const int N=2e3+20;
int n;
bool flag;
int main()
{
	while(cin>>n)
	{
		bool flag=false;
		int p;
		int index=1e7,a,b;
		for(int q=0;q<=n/7;q++)
		{
			if((n-7*q)%4==0)//p为整数 
			{
				flag=true;
				p=(n-7*q)/4;
				if(index>p+q)//位数尽量小 
				{
					index=p+q;
					a=p;
					b=q;
				}
				
			}
		}	
		if(flag==false)
		cout<<-1;
		else
		{
		
			for(int i=1;i<=a;i++)
			cout<<4;
			for(int i=1;i<=b;i++)
			cout<<7;
		}
		cout<<endl;
		
	
	}
	return 0;
}