0

问题陈述询问 i < j < k 的此类子数组的数量，这样任何两个数字的总和应大于或等于子数组中的第三个数：

我做了什么：

我从 i=0 到 n-2 运行了一个循环：我使用的基本逻辑是，如果排序子数组中的前两个元素大于或等于最大值，那么所有对都将大于任何元素。每次获得子数组时，我都会将下一个元素添加到其中并再次设置这三个变量。我正在通过 15/20 TCs，其他人正在获得 TLE：
约束：
1<=n<=10^5
1<=ai<=10^9

for(int i=0;i<n-2;i++)
{
    int r=i+2;
    vector<int> temp(inp.begin()+i,inp.begin()+r+1);
    sort(temp.begin(),temp.end());
    max_elem=temp[1];min_elem=temp[0];
    int maximum=temp[temp.size()-1];


    //cout<<max_elem<<" "<<min_elem<<"\n";

    while(r<n && max_elem+min_elem >= maximum)
    {   
        //cout<<max_elem<<" "<<min_elem<<" "<<inp[r]<<"\n";
        cnt++;
        r++;

        if(inp[r]<min_elem) {max_elem=min_elem;min_elem=inp[r];}
        else if(inp[r]<max_elem) max_elem=inp[r];
        else if(inp[r]>maximum) maximum=inp[r];

    }

}
cout<<cnt<<"\n";

样品 TC：

I1 :
5
7 6 5 3 4
O1 :
6
解释：
6个子数组满足条件：(7,6,5),(7,6,5,3),(7,6,5,3,4),( 6,5,3),(6,5,3,4),(5,3,4)。

I2 :
5
1 2 3 5 6
O2 :
3
解释:
(1,2,3),(2,3,5),(3,5,6) --(注意: 1,2,3,5 is'因为 1+2 < 5)

4

2 回答 2

0

可能存在一些错误，但这里是 O(n log n) 解决方案的总体思路：

我们保留从 startIdx 到 endIdx 的元素窗口。如果它是一个有效的子数组，这意味着我们可以扩展它，我们可以向它添加另一个元素，所以我们增加 endIdx。如果它不成立，那么无论我们扩大多少都不成立，所以我们需要通过增加startIdx来减少它。

伪代码：

multiset<int> nums;

int startIdx = 0, endIdx = 0;
int sol = 0;

while(endIdx != inp.size()) {
    if (endIdx - startIdx < 3) {
       nums.add(inp[endIdx]);  
       endIdx++;
    } else  {
       if (nums.lowestElement() + nums.secondLowestElement() < nums.highestElement()) {
          nums.remove(nums.find(inp[startIdx]));
          startIdx++;
       } else { 
            sol += endIdx - startIdx - 2; // amount of valid subarrays ending in inp[endIdx - 1]
            nums.add(inp[endIdx]);  
            endIdx++;
       }
    }
}
于 2018-06-18T17:32:03.883 回答
0

一个天真的方法是这样的，如下所示。你的逻辑是正确的，这就是我实现的。我用单遍（N）改变了排序（NlogN），只找到了2个最小和最大的数字。我还没有编译代码，不确定它是否按预期工作。它的整体复杂度为 (N*N*N)。

通过做一些额外的检查可以改善执行时间：

  • min1 + min2 >= max可以在每个内部 (k) 循环之后检查条件，如果违反单个案例则中断。

  • 如果子数组 4-7 的条件不满足，则无需检查包括 4-7 在内的任何其他子字符串。通过存储违规案例并在每次循环之前对其进行检查，可以提高整体执行时间。

    int min1;
int min2;
int max;
int count = 0;
for(int i = 2; i < n; i++){
    for(int j = 0; j < i - 2; j++){
        max = -1;
        min1 = min2 = 1000000000;
        for(int k = j; k <= i; k++){
            if(inp[k] > max)
                max = inp[k];
            if(inp[k] < min1){
                min1 = inp[k];
                continue;
            }
            if(inp[k] < min2){
                min2 = inp[k];
            }
        }
        if(min1 + min2 >= max)
            count++;
    }
}
于 2018-06-18T14:20:39.783 回答