目录

牛客_天使果冻_递推

题目解析

C++代码

Java代码

---

牛客_天使果冻_递推

天使果冻

描述：
        有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。
天使非常喜欢吃果冻，但她想把最好吃的果冻留到最后收藏。天使想知道前 x个果冻中，美味度第二大的果冻有多少美味度？

一共有 q 次询问。

注：如果最大的数有两个以上，默认第二大的等于最大的。例如， [2,3,4,2,4] 这个序列，第二大的数是4。

输入描述：

第一行一个正整数 n 。

第二行 n 个正整数 ai，用空格隔开。

第三行一个正整数 q 。

接下来的 q行，每行一个正整数 x，代表一次询问。

数据范围：1≤q≤1e5，1≤ai≤1e9，2≤x≤n≤1e5

输出描述：

输出 q 行，每行一个正整数，代表一次询问，输出前 x 个果冻中美味度第二大的值。

---

题目解析

需要两个数组绑定后排序，因此可以搞一个 pair 存一下，然后排序。

C++代码

#include <iostream>
#include <vector>
using namespace std;int main()
{int n = 0;cin >> n;vector<int> arr(n + 1);auto f = arr; // 1到i第一大auto g = arr; // 1到i第二大for(int i = 1; i <= n; ++i){cin >> arr[i];}f[1] = arr[1];for(int i = 1; i <= n; ++i){int x = arr[i];f[i] = max(f[i - 1], x);if(x >= f[i - 1])g[i] = f[i - 1];else if(x >= g[i - 1])g[i] = x;else g[i] = g[i - 1];}int q = 0;cin >> q;while(q--){int n = 0;cin >> n;cout << g[n] << endl;}return 0;
}

Java代码

import java.util.*;
public class Main
{public static void main(String[] args){Scanner in = new Scanner(System.in);int n = in.nextInt();int[] arr = new int[n + 1];for(int i = 1; i <= n; i++){arr[i] = in.nextInt();}// 更新最⼤值以及次⼤值数组int[] f = new int[n + 1];int[] g = new int[n + 1];f[1] = arr[1];for(int i = 2; i <= n; i++){int x = arr[i];f[i] = Math.max(f[i - 1], x);if(x >= f[i - 1])g[i] = f[i - 1];else if(x >= g[i - 1])g[i] = x;elseg[i] = g[i - 1];}int q = in.nextInt();while(q-- != 0){int x = in.nextInt();System.out.println(g[x]);}}
}