第十四届蓝桥杯三月真题刷题训练——第 27 天
目录
第 1题:数学考试_前缀和
代码:
package 第十四届蓝桥杯三月真题刷题训练.day27;
import java.io.*;
/**
* @author yx
* @date 2023-03-30 20:44
*/
public class 数学考试 {
static PrintWriter out =new PrintWriter(System.out);
static BufferedReader ins=new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in=new StreamTokenizer(ins);
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
*
* 输出
* out.print();
* out.flush();
*
* 读文件:
* BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
* String s = br.readLine();s读取每一行数据
* if (s == null)break;读取文件终止的语句
**/
public static void main(String[] args) throws IOException {
in.nextToken();
int T=(int)in.nval;
while (T--!=0) {
String[] strings = ins.readLine().split(" ");
int n=Integer.parseInt(strings[0]);
int k=Integer.parseInt(strings[1]);
long[] nums=new long[n+1];
String[] strings1=ins.readLine().split(" ");
long max_left=Long.MIN_VALUE;
long max=Long.MIN_VALUE;
for (int i = 1; i <= n; i++) {
//前缀和
nums[i]+=nums[i-1]+Long.parseLong(strings1[i-1]);
}
for (int i = 0; i <= n-2*k; i++) {
max_left=Math.max(nums[i+k]-nums[i],max_left);
max=Math.max(max,max_left+nums[i+2*k]-nums[i+k]);
}
out.println(max);
}
out.flush();
}
}
第 2 题:地标访问_二分
题目背景
改编自 USACO2007Nov 铜组 Exploration
题目描述
贝西在一条道路上旅行,道路上有许多地标,贝西想要在日落之前访问尽可能多的路标。将道路视为一条数轴,贝西从原点出发,道路上有 n(1≤n≤5×10^4)个地标,每个地标有一个坐标 xi(∣xi∣≤105)且地标的坐标各不相同,t(1≤T≤109)分钟之后将会日落。
输入格式
第一行:两个整数 t,n。
第二行至第 n+1 行:地标的坐标 xi。
输出格式
一个整数,贝西能访问的最多的地标数
输入输出样例
输入 #1
25 14 16 8 -7 3 10 -15 -17 6 -12 14 -13 2 9 -5输出 #1
8说明/提示
1、贝西日落时不用回到原点。
2、与原模拟水题不同。
3、数据较原题有所修改
代码:
package 第十四届蓝桥杯三月真题刷题训练.day27;
import java.io.*;
import java.util.Arrays;
/**
* @author yx
* @date 2023-03-30 21:04
*/
public class 地标访问 {
static PrintWriter out = new PrintWriter(System.out);
static BufferedReader ins = new BufferedReader(new InputStreamReader(System.in));
static StreamTokenizer in = new StreamTokenizer(ins);
static int T;
static int[] nums;
static int n;
/**
* 输入
* in.nextToken()
* int a= (int)in.nval;
* <p>
* 输出
* out.print();
* out.flush();
* <p>
* 读文件:
* BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("C:\\Users\\yx\\Desktop\\primes.txt")));
* String s = br.readLine();s读取每一行数据
* if (s == null)break;读取文件终止的语句
**/
public static void main(String[] args) throws IOException {
in.nextToken();
T = (int) in.nval;
in.nextToken();
n = (int) in.nval;
nums = new int[n];
for (int i = 0; i < n; i++) {
in.nextToken();
nums[i] = (int) in.nval;
}
Arrays.sort(nums);
int l = 0;
int r = n;
int ans = 0;
//二分枚举答案
while (l <= r) {
//二分
int mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
System.out.print(ans);
}
//
static boolean check(int m) {
for (int i = 0; i < n-m+1; i++) {
//左端点和右端点同号
if((long)nums[i]*nums[i+m-1]>0){
if (Math.max(Math.abs(nums[i]), Math.abs(nums[i + m - 1]))<=T) {
return true;
}
}else {//左端点和右端点异号
if(Math.min(Math.abs(nums[i]), Math.abs(nums[i + m - 1]))*2+Math.max(Math.abs(nums[i]), Math.abs(nums[i + m - 1]))<=T){
return true;
}
}
}
return false;
}
}