求助!只有46分
查看原帖
求助!只有46分
541069
SuperCowHorse楼主2022/4/9 16:21
#include<bits/stdc++.h>
#define lo long long
using namespace std;
char s[105];
int len,n,ans=2e9,sum[105];
bool pd(int x,int y)
{
	lo cnt=0;
	for(int i=x+1;i<=len;++i)
		cnt=cnt*10+sum[i];
	if(y+cnt<n) return 1;
	return 0;
}
bool dp(int x,int y)
{
	lo cnt=0;
	for(int i=x+1;i<=len;++i)
		cnt+=sum[i];
	if(cnt+y>n) return 1;
	return 0;
}
void dfs(int x,int y,int z,int now)
{
	if(y>=ans) return;
	if(now>n) return;
	if(pd(x,now+z)||dp(x,now+z)) return;
	if(now==n){ans=y;return;}
	if(x>len) return;
	dfs(x+1,y+1,sum[x+1],now+z);
	dfs(x+1,y,z*10+sum[x],now);
}
int main()
{
	cin>>s+1;
	scanf("%d",&n);
	len=strlen(s+1);
	for(int i=1;i<=len;++i)
		sum[i]=s[i]-48;
	dfs(1,0,sum[1],0);
	if(ans!=2e9) printf("%d",ans-1);
	else printf("-1");
	return 0;
}
2022/4/9 16:21
加载中...