蓝桥杯2018年第九届真题-防御力-题解（Java代码）

解题思路:

B=A^(ln3/ln2)

指数大于一的幂函数。（想象二次函数的正半周图形走向）

要让函数增加最多。需要B在开始时增加最多，然后让A在最后增加得最多。

系统样例应该有错误。

样例

3 0
7 11 13

000

和样例

3 0
13 11 7

000

都应该输出

A1
A2
A3
E

而系统的第二个样例却是输出的

000
A3
A2
A1
E

并不符合题目字典序最小的要求。

注意事项:

如上，注意题目要求的字典序最小。

参考代码:

可以通过系统样例的代码（这个代码是错的，并不符合题目字典序最小的要求）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static void swap(int[] arr, int i, int j) {
		int t = arr[i];
		arr[i] = arr[j];
		arr[j] = t;
	}

	static void reverse(int[] arr, int i, int j) {
		int j_1 = j - 1;
		for (int ii = 0, end = (j - i) / 2; ii < end; ++ii) {
			swap(arr, i + ii, j_1 - ii);
		}
	}

	static int[] get_sorted_index(final int[] arr) {
		int len = arr.length;
		ArrayList index = new ArrayList(len);
		for (int i = 0; i < len; ++i)
			index.add(i);
		Collections.sort(index, new Comparator() {
			public int compare(Integer o1, Integer o2) {
				return arr[o1] - arr[o2];
			}
		});
		int[] _index = new int[len];
		for (int i = 0; i < len; ++i)
			_index[i] = index.get(i);

		return _index;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();

		int[] a = new int[n1];
		int[] b = new int[n2];

		for (int i = 0; i < n1; ++i)
			a[i] = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < n2; ++i)
			b[i] = sc.nextInt();
		sc.nextLine();

		char[] order = sc.nextLine().toCharArray();
		int[] best = new int[order.length];

		int[] sorted_a_index = get_sorted_index(a);
		int[] sorted_b_index = get_sorted_index(b);

		int a_s = 0;
		int b_e = sorted_b_index.length;

		int b_s = 0;

		for (int i = 0; i < order.length;) {
			int j = i + 1;
			while (j < order.length && order[i] == order[j])
				++j;
			int len = j - i;
			if ('0' == order[i]) {
				System.arraycopy(sorted_a_index, a_s, best, b_s, len);
				a_s += len;
			} else {
				System.arraycopy(sorted_b_index, b_e - len, best, b_s, len);
				reverse(best, b_s, b_s + len);
				b_e -= len;
			}
//			Arrays.sort(best, b_s, b_s + len);
			b_s += len;
			i = j;
		}
		for (int i = 0; i < order.length; ++i) {
			System.out.print((char) ('A' + order[i] - '0'));
			System.out.println(best[i] + 1);
		}
		System.out.println('E');

		return;
	}
}

正确代码（需要对相同的样例进行排序）

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
	static int[] get_sorted_index(final int[] arr) {
		int len = arr.length;
		ArrayList index = new ArrayList(len);
		for (int i = 0; i < len; ++i)
			index.add(i);
		Collections.sort(index, new Comparator() {
			public int compare(Integer o1, Integer o2) {
				return arr[o1] - arr[o2];
			}
		});
		int[] _index = new int[len];
		for (int i = 0; i < len; ++i)
			_index[i] = index.get(i);

		return _index;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n1 = sc.nextInt();
		int n2 = sc.nextInt();

		int[] a = new int[n1];
		int[] b = new int[n2];

		for (int i = 0; i < n1; ++i)
			a[i] = sc.nextInt();
		sc.nextLine();
		for (int i = 0; i < n2; ++i)
			b[i] = sc.nextInt();
		sc.nextLine();

		char[] order = sc.nextLine().toCharArray();
		int[] best = new int[order.length];

		int[] sorted_a_index = get_sorted_index(a);
		int[] sorted_b_index = get_sorted_index(b);

		int a_s = 0;
		int b_e = sorted_b_index.length;

		int b_s = 0;

		for (int i = 0; i < order.length;) {
			int j = i + 1;
			while (j < order.length && order[i] == order[j])
				++j;
			int len = j - i;
			if ('0' == order[i]) {
				System.arraycopy(sorted_a_index, a_s, best, b_s, len);
				a_s += len;
			} else {
				System.arraycopy(sorted_b_index, b_e - len, best, b_s, len);
//				reverse(best, b_s, b_s + len);
				b_e -= len;
			}
			Arrays.sort(best, b_s, b_s + len);
			b_s += len;
			i = j;
		}
		for (int i = 0; i < order.length; ++i) {
			System.out.print((char) ('A' + order[i] - '0'));
			System.out.println(best[i] + 1);
		}
		System.out.println('E');

		return;
	}
}