手机网站的宽度,南京做网站建设的公司排名,网站建设技术经理岗位职责,wordpress数据库配置文件目录
牛客_天使果冻_递推
题目解析
C代码
Java代码 牛客_天使果冻_递推
天使果冻
描述#xff1a; 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻#xff0c;但她想把最好吃的果冻留到最后收藏。天使想知道前 x个果冻中#xff0c;美味…目录
牛客_天使果冻_递推
题目解析
C代码
Java代码 牛客_天使果冻_递推
天使果冻
描述 有 n 个果冻排成一排。第 i 个果冻的美味度是 ai。 天使非常喜欢吃果冻但她想把最好吃的果冻留到最后收藏。天使想知道前 x个果冻中美味度第二大的果冻有多少美味度
一共有 q 次询问。
注如果最大的数有两个以上默认第二大的等于最大的。例如 [2,3,4,2,4] 这个序列第二大的数是4。
输入描述 第一行一个正整数 n 。 第二行 n 个正整数 ai用空格隔开。 第三行一个正整数 q 。 接下来的 q行每行一个正整数 x代表一次询问。 数据范围1≤q≤1e51≤ai≤1e92≤x≤n≤1e5 输出描述 输出 q 行每行一个正整数代表一次询问输出前 x 个果冻中美味度第二大的值。 题目解析
需要两个数组绑定后排序因此可以搞一个 pair 存一下然后排序。
C代码
#include iostream
#include vector
using namespace std;int main()
{int n 0;cin n;vectorint 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]);}}
}
