这个问题的解决方案有什么问题

Question

我正在尝试解决： https://www.spoj.com/problems/ANARC05B/

我正在使用二进制搜索来解决这个问题。我想我遵循了正确的方法。谁能帮我做一个会失败的测试用例？

下面是我的代码，它通过了示例测试用例，我没有发现我的代码有问题，但仍然不确定为什么我得到 WA！！请帮忙！！

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;

int BinarySearch(vector<int> arr, int key)
{
    int minNum = 0;
    int maxNum = arr.size() - 1;

    while (minNum <= maxNum)
    {
        int mid = (minNum + maxNum) / 2;
        if (key == arr[mid])
        {
            return mid;
        }
        else if (key < arr[mid])
        {
            maxNum = mid - 1;
        }
        else
        {
            minNum = mid + 1;
        }
    }
    return -1;
}

signed long Solve(vector<int> First, vector<int> Second)
{

    // Find the intersections in both the arrays and store the indices for them.
    vector<int> FirstInterIndices;
    vector<int> SecondInterIndices;
    for (int i = 0; i < Second.size(); i++)
    {
        int idx = BinarySearch(First, Second[i]);
        if (idx != -1)
        {
            SecondInterIndices.push_back(i);
            FirstInterIndices.push_back(idx);
        }
    }

    if (FirstInterIndices.empty())
    {
        FirstInterIndices.push_back(FirstInterIndices.size() - 1);
        SecondInterIndices.push_back(SecondInterIndices.size() - 1);
    }
    //Find Intersections ends

    //Calc the sum upto intersections in both the arrays and store them
    vector<signed long> FirstInterSum;
    vector<signed long> SecondInterSum;

    for (int i = 0; i < SecondInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = SecondInterIndices[i - 1] + 1;
        }
        for (; k <= SecondInterIndices[i]; k++)
        {
            Sum += (signed long)Second[k];
        }
        SecondInterSum.push_back(Sum);
    }
    signed long SumLeft = 0;
    if (SecondInterIndices.size() > 0)
    {
        for (int k = SecondInterIndices[SecondInterIndices.size() - 1] + 1; k < Second.size(); k++)
        {
            SumLeft += (signed long)Second[k];
        }
        SecondInterSum.push_back(SumLeft);
    }


    for (int i = 0; i < FirstInterIndices.size(); i++)
    {
        int k = 0;
        signed long Sum = 0;
        if (i > 0)
        {
            k = FirstInterIndices[i - 1] + 1;
        }
        for (; k <= FirstInterIndices[i]; k++)
        {
            Sum += (signed long)First[k];
        }
        FirstInterSum.push_back(Sum);
    }

    if (FirstInterIndices.size() > 0)
    {
        SumLeft = 0;
        for (int k = FirstInterIndices[FirstInterIndices.size() - 1] + 1; k < First.size(); k++)
        {
            SumLeft += (signed long)First[k];
        }
        FirstInterSum.push_back(SumLeft);
    }
    // Calc sum upto intersections ENDs

    // Compare corresponding elements (sum upto intersections) and add the max from First and Second
    signed long MaxSum = 0;
    int j = 0;
    for (; j < FirstInterSum.size(); j++)
    {
        if (j < SecondInterSum.size())
        {
            if (FirstInterSum[j] > SecondInterSum[j])
            {
                MaxSum += FirstInterSum[j];
            }
            else
            {
                MaxSum += SecondInterSum[j];
            }
        }
    }

    // If Any sum exists after last intersection add that as well.
    if (j < FirstInterSum.size())
    {
        MaxSum += FirstInterSum[FirstInterSum.size() - 1];
    }
    if (j < SecondInterSum.size())
    {
        MaxSum += SecondInterSum[SecondInterSum.size() - 1];
    }
    return MaxSum;
}

vector<int> getArray()
{
    vector<int> res;
    int n;
    cin >> n;
    int x;
    for (int i = 0; i < n; i++)
    {
        cin >> x;
        res.push_back(x);
    }
    return res;
}

int main()
{
    for (;;)
    {
        vector<int> First = getArray();
        if (First.size() == 0)
            return 0;
        vector<int> Second = getArray();
        cout << Solve(First, Second);
    }
    return 0;
}

Answer 1

但是这道题既不需要二分查找也不需要动态规划（网站上有标注），可能线性时间就可以解决（最好）

制作两个索引 - 第一个数组和第二个数组。

在每一步移动指向较小元素的索引（就像在合并排序的合并过程中）。移动时，计算当前和（交点之间的和）。

当两个指标指向相同的值时，您就找到了交点。从两个数组中选择较大的当前总和，将其与交集项添加到结果中，将总和重置为零。

伪代码草图

if a[ia] < b[ib]) 
   asum += a[ia++]
else 
  if a[ia] > b[ib]) 
      bsum += b[ib++]
  else
     result += max(asum, bsum) + a[ia]
     asum = bsum = 0
     ia++
     ib++

Answer 2

你得到WA是因为输出格式不正确。我运行您的代码，输出如下所示：

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0450
2100
Program ended with exit code: 0

但预期的格式应该是：

13 3 5 7 9 20 25 30 40 55 56 57 60 62
11 1 4 7 11 14 25 44 47 55 57 100
4 -5 100 1000 1005
3 -12 1000 1001
0
450
2100
Program ended with exit code: 0

区别是0和450不在同一行。

这个问题的解决方案有什么问题

What is wrong with the solution to this problem

algorithm

binary-search