5月场Java模拟考编程题
1. 排序子序列
代码解析
: 使用一个变量来表示当前递增或递减, 遍历一遍数组即可
import java.util.Scanner;
/**
* Created by zbyte on 17-5-19.
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int f = -1; // 标志: -1开始, 1递增, 2递减
int last = sc.nextInt();
int res = 0;
for (int i = 1; i < n; i++) {
int now = sc.nextInt();
if (f == -1) {
if (now > last) {
f = 1;
} else if (now < last) {
f = 2;
}
} else if (f == 1) {
if (now < last) {
f = -1;
res++;
}
} else {
if (now > last) {
f = -1;
res++;
}
}
last = now;
}
res++;
System.out.println(res);
}
}
2. 组队竞赛
代码解析
: 将数组排序, 如例子n=2, 数组a排序后为1 2 5 5 5
8, 则对数组下标为n, n+2, ... , n*3-2的值求和即为答案(贪心)
import java.util.Arrays;
import java.util.Scanner;
/**
* Created by zbyte on 17-5-19.
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n*3];
for (int i = 0; i < n*3; i++) {
a[i] = sc.nextInt();
}
Arrays.sort(a);
long res = 0;
for (int i = n; i < n*3; i += 2) {
res += a[i];
}
System.out.println(res);
}
}
3. 训练部队
代码解析
: 先对数组排序, 按战斗力排, 战斗力相等后按潜力值排. 之后找到x+y最大值的位置,
然后倒序往回对y-x>0的值求和, 得到最终结果. cha值的意义: 当x1=6,y1=8; x2=7;
通过cha值可以从战斗力为7开始往回遍历, 得到最终结果15
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
/**
* Created by zbyte on 17-5-19.
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Entity[] a = new Entity[n];
for (int i = 0; i < n; i++) {
a[i] = new Entity(sc.nextInt(), sc.nextInt());
}
Arrays.sort(a, new Comparator<Entity>() {
@Override
public int compare(Entity o1, Entity o2) {
return o1.x-o2.x!=0 ? o1.x-o2.x : o1.y-o2.y;
}
});
int max = 0; //x+y的最大值
int index = 0; // 下标
int cha = 0; // 差值
for (int i = 0; i < n; i++) {
if (a[i].x + a[i].y >= max || a[i].x + a[i].y + cha >= max) {
max = a[i].x + a[i].y;
cha = a[i].y - a[i].x;
index = i;
}
}
long res = max;
for (int i = index-1; i >= 0 ; i--) {
if (a[i].y > a[i].x) {
res += a[i].y - a[i].x;
}
}
System.out.println(res);
}
static class Entity {
int x;
int y;
public Entity(int x, int y) {
this.x = x;
this.y = y;
}
}
}
