问题- 来自利沃夫动物园的小象非常喜欢幸运数字。大家都知道幸运数字是正整数，其十进制表示只包含幸运数字4和7。例如数字47、744、4是幸运数字，而5、17、467则不是。
令 F4(X) 为 X 的十进制表示的位数 4，F7(X) 为 X 的十进制表示的位数 7。例如，F4(456) = 1, F4(444) = 3, F7(1) = 0, F7(747) = 2。小象想知道最大的乘积 F4(X) ∙ F7(X)，其中 L ≤ X ≤ R。换句话说，他想知道最大值{F4(X) ∙ F7(X) : L ≤ X ≤ R}。
1 <= L <= R <= 10 18
示例：1) 对于范围，1 100答案将是 1 {47,74}
2) 4199 6000 答案将是 4 {4747, 4477}
我觉得我的代码是正确的，但是在提交它时得到了错误的答案。谁能帮我找出到底出了什么问题？
我的算法不会错（它非常简单）。我已经仔细检查了实现（它处理了所有可能的情况）。很难相信某些输入会出错。
这是 C++ 代码：
#include <cstdio>
#include <cstring>
using namespace std;
char buf1[20],buf2[20];
int *L, *R, *ans, len, ansn;
bool flagL, flagR;
inline int count(int n)
{
int a=0,c=0;
for(;a<len;a++) if(ans[a] == n) c++;
return c;
}
inline int max(int a, int b) { return a>b ? a:b; }
inline int min(int a, int b) { return a<b ? a:b; }
inline void f(int i, int n)
{
int a=0,n4=0,n7=0,t;
for(;a<=i;a++) if(ans[a] == 4) n4++; else if(ans[a] == 7) n7++;
while(n)
{
if(n4 == n7)
{
n4 += n/2;
n7 += (n-n/2);
break;
}
else if(n4 > n7)
{
t = min(n,n4-n7);
n -= t;
n7 += t;
}
else if(n7 > n4)
{
t = min(n,n7-n4);
n -= t;
n4 += t;
}
}
ansn = max(ansn,n4*n7);
}
void solve(int i, bool flagL, bool flagR)
{
while(i<len)
{
if(flagL && !flagR)
{
if(4 > L[i])
{
f(i-1,len-i);
return;
}
if(4 == L[i])
{
ans[i] = 4;
solve(i+1, 1, 0);
ans[i] = 7;
f(i,len-i-1);
return;
}
if(7 > L[i])
{
ans[i] = 7;
f(i,len-i-1);
return;
}
if(7 == L[i])
{
ans[i] = 8;
f(i,len-i-1);
ans[i] = 7;
i++;
continue;
}
// else
ans[i] = 9;
if(ans[i] > L[i])
{
f(i,len-i-1);
return;
}
else
{
i++;
continue;
}
}
if(!flagL && flagR)
{
if(7 < R[i])
{
f(i-1,len-i);
return;
}
if(7 == R[i])
{
ans[i] = 4;
f(i,len-i-1);
ans[i] = 7;
i++;
continue;
}
if(4 < R[i])
{
ans[i] = 4;
f(i,len-i-1);
return;
}
if(4 == R[i])
{
ans[i] = 3;
f(i,len-i-1);
ans[i] = 4;
i++;
continue;
}
// else
ans[i] = 0;
if(ans[i] < R[i])
{
f(i,len-i-1);
return;
}
else
{
i++;
continue;
}
}
if(flagL && flagR)
{
if(R[i] - L[i] == 1)
{
ans[i] = L[i];
solve(i+1,1,0);
ans[i]++;
solve(i+1,0,1);
return;
}
bool four = 4 > L[i] && 4 < R[i];
bool sev = 7 > L[i] && 7 < R[i];
if (four && sev)
{
f(i-1,len-i);
return;
}
else if (four && !sev)
{
ans[i] = 4;
f(i,len-i-1);
}
else if (!four && sev)
{
ans[i] = 7;
f(i,len-i-1);
}
if (L[i] == 4 || L[i] == 7 || R[i] == 4 || R[i] == 7)
{
if(L[i] == R[i]) { ans[i] = L[i]; i++; continue; }
if(L[i] == 4 && R[i] == 7)
{
ans[i] = 4;
solve(i+1,1,0);
ans[i] = 7;
solve(i+1,0,1);
ans[i] = 5;
f(i,len-i-1);
return;
}
if(R[i] - L[i] >= 2)
{
ans[i] = L[i]+1;
f(i,len-i-1);
if(L[i] == 4 || L[i] == 7)
{
ans[i] = L[i];
solve(i+1,1,0);
}
if(R[i] == 4 || R[i] == 7)
{
ans[i] = R[i];
solve(i+1,0,1);
}
return;
}
}
else
{
if (R[i] - L[i] >= 2)
{
ans[i] = L[i]+1;
f(i,len-i-1);
return;
}
ans[i] = L[i];
}
}
i++;
} // end of while
ansn = max(ansn, count(4)*count(7));
}
int main()
{
int a,t; scanf("%d\n",&t);
while(t--) // test cases
{
scanf("%s %s",&buf1,&buf2);
len = strlen(buf2);
L = new int[len];
R = new int[len];
ans = new int[len];
for(a=0;a<len;a++) R[a] = buf2[a]-48;
for(a=0;a<len-strlen(buf1);a++) L[a] = 0;
int b=a;
for(;a<len;a++) L[a] = buf1[a-b]-48;
flagL = flagR = 1; ansn = 0;
solve(0,1,1);
printf("%d\n",ansn);
}
return 0;
}
算法：
首先，将 L,R 的数字放入长度 = no 的数组 L[],R[] 中。R 中的数字。并初始化一个数组 ans[] 以跟踪答案整数（F4(ans)*F7(ans) 最大的整数）。
在左侧将 L 填充 0，使其长度等于 R。（所以 1,100 变为 001,100）这是在 main() 本身中完成的，然后调用solve()
真正的逻辑：运行一个循环，for i in range(0,len(R)) 对于每个 i，比较 L[i] 和 R[i]
变量flagL和flagR告诉你是否需要分别检查 L 和 R。
假设 L[], R[] 最初是：238 967 首先我们需要从第 0 个索引开始检查它们（因此 solve(0,1,1) 或 solve(0,true,true) ）。
现在 4 和 7 都落在L [0] 和 R[0] 之间。因此，{4,7} 的任何排列都可以放在 3 位数字中，而 ans[] 不会超出范围[L,R]。所以答案是2。
如果范围是：238 和 545
只有 4 会落在2 和 5之间，所以我们将 4 放在 ans[0] 中，并且 {4,7} 的任何排列都可以放在其余位置。所以答案又是2。
如果范围是：238 和 410
4 和 7 都不在 L[0] 和 R[0] 之间。但请注意，R[0] 为 4。
所以我们现在有 2 个选择，4 和 L[0]+1（这就是递归的用武之地）
为什么 L[0]+1 ？因为如果我们将 L[0]+1 放在 ans[0] 中，ans[0] 将落在 L[0] 和 R[0] 之间（对于这个 R[0] - L[0] >= 2）并且无论我们在剩余的数字中输入什么，ans[] 都不会超出范围。但是我们还必须检查 ans[0] 是否为 4。在最后一个示例中，它不会有帮助，但如果 R >= 477，它就会有帮助。
所以答案是 1。（如果 R >= 477，则为 2）
让我们讨论另一个例子：
范围：4500 5700
因为 R[0] 和 L[0] 仅相差 1，我们必须检查两者，一次是 ans[i] = L[i]，然后是 ans[i] = R[i]（或 ans[i ]++)
现在，如果我们检查 ans[i] = 4，我们将不必再比较 ans[i] 和 R[i]，因为 ans[0] < R[0]，因此ans将始终 < R。所以我们像这样递归调用solve()：solve(i+1, true, false)
下一次，当 ans[0] = R[0] 时，我们就不必将 ans 与 L 进行比较（因为 ans > L，我们在剩下的 2 个地方放什么）。然后我们像这样调用solve()：solve(i+1, false, true)。
您会了解它是如何工作的，而且，如果您查看我的代码，则不会遗漏任何可能的测试用例。我不知道我为什么要获得 WA。
PS：安德鲁指出了错误。条件顺序错误。if 块4 == L[i]应该在 if 块之前7 > L[i]。现在代码可以正常工作了。