codeforce每日一题
题目链接
题目分数:1400
题目描述
输入 $n(3≤n≤3000)$ 和长度均为 $n$ 的数组 $a(1≤a[i]≤1e9)$ 和数组 $b(1≤b[i]≤1e8)$。
输出在满足 $i<j<k$ 且 $a[i]<a[j]<a[k]$ 的前提下,$b[i]+b[j]+b[k]$ 的最小值。
如果不存在这样的 $(i,j,k)$,输出 $-1$。
样例
输入样例1
5
2 4 5 4 10
40 30 20 10 40
输出样例1
90
输入样例2
3
100 101 100
2 4 5
输出样例2
-1
算法
(暴力枚举) $O(n^2)$
直接枚举$a[j]$,再找前面小于$a[j]$的最小$b[i]$,后面大于$a[j]$的最小$b[k]$。
C++ 代码
// https://www.acwing.com/blog/content/34755/
#include<bits/stdc++.h>
#define rep(i, a, b) for(int i=a;i<=b;i++)
#define per(i, a, b) for(int i=b;i>=a;i--)
#define endl '\n'
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define pd push_back
#define SZ(a) (int)a.size()
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
typedef pair<double, double> PDD;
const int N = 1e5 + 10, M = N * 2, INF = 0x3f3f3f3f;
int n, m;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
vector<LL> a(n), b(n);
rep(i, 0, n - 1) cin>>a[i];
rep(i, 0, n - 1) cin>>b[i];
vector<LL> w(n, 0);
stack<LL> stk;
rep(i, 0, n - 1)
{
while(stk.size() && a[stk.top()] >= a[i]) stk.pop();
if(!stk.size()) w[i] = 1e18;
else w[i] = min(b[stk.top()], w[stk.top()]);
}
while(stk.size()) stk.pop();
LL res = 1e18;
rep(i, 0, n - 1)
{
while(stk.size() && a[stk.top()] >= a[i]) stk.pop();
if(stk.size())
{
if(w[stk.top()] != b[stk.top()]) res = min(res, w[stk.top()] + b[i]);
}
}
cout<<res<<endl;
return 0;
}