主页 / 问题 / 728131
Accepted
Paul Shipilov
Asked:2020-10-08 21:58:17 +0000 UTC2020-10-08 21:58:17 +0000 UTC

查找不大于第i个且其索引大于i的元素的第一次出现的算法优化

  • 772

我解决了这个问题，在这里我得到了 time_lim，我需要优化这个算法，让它通过 2 次测试，4-5 毫秒是不够的。该算法查找不大于第 i 个且其索引大于 i 的元素的第一次出现，如果不存在，则输出 -1。

 int i(0),j(0);
 int n1;
 v_t v;  //вектор типа int
 auto it(v.begin());

bool perd(int n)
{
    ++j;
    if(n1>n)
    {
        cout<<j<<' ';
        return true;
    }
    return false;
}

void fun(int n)
{
    ++i;
    n1=n;
    it=find_if(v.begin()+i,v.end(),perd);
    if(it==v.end())
        cout<<-1<<' ';
    j=i;
}

void funcin(int &n)
{
    cin>>n;
}

int main()
{
    cin >> n1;
    v.resize(n1);
    for_each(v.begin(),v.end(),funcin);
    for_each(v.begin(),v.end(),fun);
    return 0;
}

任务全文：

Lineland是一个一维世界，是一条直线，上面有N个城市，从0到N-1依次编号。从第一个城市到零一个的方向称为西，而在相反的方向 - 东。

当危机突然在莱恩兰开始时，世界上所有的居民都开始经历深深的动荡。谣言开始在莱兰兰流传，东部的生活比西部的好。大林地大迁徙就这样开始了。世界各地的居民，在整个城市中，向东走，离开他们的家乡街道，一直移动，直到他们来到一个平均生活成本低于他们自己的城市。

c++

1 个回答

  1. Best Answer

    您的二次复杂度算法。我刚刚想出了一个有趣的算法来解决这个问题，它应该很快，它是线性的：

    我们将使用一堆数字（一个可以从元素末尾添加和删除的简单向量）。该算法的本质是我们找到元素严格增加的部分，如果该部分突然中断，即 突然该元素小于前一个元素，则可以将前一个递增部分的末尾部分分配给每个人，该元素是所有元素中最接近的较小元素。那些。这是算法 - 我们沿着数组从左到右移动，同时检查堆栈顶部有一个更大的（当前）元素并且堆栈不为空，然后我们将元素推出堆栈并分配给这个元素（堆栈）最接近它的元素是我们可观察到的数组元素。最后，如果堆栈不为空，则我们为其所有元素分配没有找到适合它们的元素，即 放-1。

    这样的算法是线性的（相对于数组 N 的大小），因为 它只遍历数组的所有元素一次，同时从堆栈中进行不超过 N 次加法和位移以及 2*N 次比较。这是 C++ 中的完整算法（在 C++和Python中在线运行）：

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

int main() {
    // nums - входные числа, stck - стэк, result - ответ
    vector<int> nums, stck, result;

    // Заполняем входной массив, можно через std::cin.
    nums = {1,2,3,2,1,4,2,5,3,1}; // Выдаёт -1 4 3 4 -1 6 9 8 9 -1
    result.resize(nums.size(), -1);

    // Основной алгоритм.
    for (size_t i = 0; i < nums.size(); ++i) {
        while (!stck.empty() && nums[stck.back()] > nums[i]) {
            result[stck.back()] = i;
            stck.pop_back();
        }
        stck.push_back(i);
    }

    // Выводим результат.
    for (size_t i = 0; i < result.size(); ++i) {
        cout << result[i] << " ";
    }

    return 0;
}
    • 6

相关问题