3.19 阿里笔试第二题C++

第一题比较常规就不写了。

第二题大意是：

在一个数组中 寻找 且 的一组序列，再这一系列中使得 最小。 数据量 3000。

之前题目给错了 a写成了小于等于，被我用样例测出来了。 看复杂度肯定过不了，先骗分暴力了一发 过了 83.3%。

想了 二十分钟大概有了思路，写了个，过了。

思路：

使用一个数组: 表示 以j结尾的所有 中， 的最小值，遍历需要。

再用遍历找到的值， 即为所求。

代码如下，已AC：

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

vector<long long> a;
vector<long long> b;
vector<long long> c;
int main()
{
    int n;
    const long long sum = 0x7fffffff;
    cin>>n;
    a.resize(n);
    b.resize(n);
    c.resize(n, sum);
    for(int i=0; i<n; i++)
        cin>>a[i];
    for(int i=0; i<n; i++)
        cin>>b[i];
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(a[i] < a[j])
            {
                c[j] = min(c[j], b[i] + b[j]);
            }
        }
    }
    bool vis = false;
    long long ans = 0x7fffffff;
    for(int i=0; i<n; i++)
    {
        for(int j=i+1; j<n; j++)
        {
            if(a[i] < a[j] && c[i] != sum)
            {
                vis = true;
                ans = min(ans, c[i] + b[j]);
                //cout<<i<<' '<<j<<' '<<c[i]<<' '<<b[j]<<' '<<min(ans, c[i] + b[j])<<endl;
            }
        }
    }
    if(!vis)
        cout<<-1<<endl;
    else
        cout<<ans<<endl;
    return 0;
}
/*
8
9 8 6 7 7 2 9 2
9 1 10 8 6 4 8 6
*/