第八届蓝桥杯省赛JavaC组真题——详细答案对照(完整版)-3

package action;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
public class demo {
  static String start;
  static String end;
  static Queue<State> q = new LinkedList<>();
  static Set<String> set = new HashSet<>();// 过滤纸重复的队列模式
  static int[] dir = { 1, 2, 3, -1, -2, -3 };// 六种状态，-3表示向左边跳三个距离
  public static String swap(int a, int b, String str) {// 交换str中 a、b 两处的字符
  char cs[] = str.toCharArray();
  char temp = cs[a];
  cs[a] = cs[b];
  cs[b] = temp;
  str = new String(cs);
  return str;
  }
  public static int bfs(String now, int pos, int step) {
  q.add(new State(now, pos, step));
  while (!q.isEmpty()) {
    State curState = q.poll();
    if (curState.pattern.equals(end))
    return curState.step;
    if (set.contains(curState.pattern)) {
    continue;
    } else {
    set.add(curState.pattern);
    }
    for (int i = 0; i < dir.length; i++) {// 六个状态
    int nextPos = curState.pos + dir[i];// 下一个空杯的位置
    if (nextPos < curState.pattern.length() && nextPos >= 0) {// 得在合法的位置
      String temp = curState.pattern;// 记录当前的队列状态
      String nextPattern = swap(curState.pos, nextPos, temp);// 交换，产生新的队列模式
      State nextState = new State(nextPattern, nextPos, curState.step + 1);
      if (!set.contains(nextPattern))
      q.add(nextState);
    }
    }
  }
  return -1;
  }
  public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  start = sc.nextLine();
  end = sc.nextLine();
  sc.close();
  int pos = 0;
  for (int i = 0; i < start.length(); i++) {
    if (start.charAt(i) == '*') {
    pos = i;
    break;
    }
  }
  System.out.println(bfs(start, pos, 0));
  }
}
class State {
  String pattern;// 当前队列模式
  int pos;// * 所在的索引
  int step;// 从初始队列模式到当前队列模式经过的步数
  public State(String now, int pos, int step) {
  this.pattern = now;
  this.pos = pos;
  this.step = step;
  }
}

package action;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class demo {
  public static void main(String[] arg) {
  solve();
  }
  static StringTokenizer ST;
  static BufferedReader BR;
  static PrintWriter PW;
  static String next() {
  while (ST == null || !ST.hasMoreTokens()) {
    try {
    ST = new StringTokenizer(BR.readLine());
    } catch (Exception e) {
    // TODO: handle exception
    throw new RuntimeException(e);
    }
  }
  return ST.nextToken();
  }
  static int nextInt() {
  return Integer.parseInt(next());
  }
  public static void solve() {
  BR = new BufferedReader(new InputStreamReader(System.in));
  PW = new PrintWriter(System.out);
  int m = nextInt(), n = nextInt();
  Pair a[] = new Pair[n + 10];
  Triple cr[] = new Triple[n + 10];
  cr[0] = new Triple();
  // 正向处理出加到第i块的状态，Triple记忆第i块右下坐标(x,y)和第i块缩放后的高度h
  for (int i = 1; i <= n; i++) {
    // 创建
    Triple tmp = new Triple(cr[i - 1]);
    // 如果这一行装不下，就置零换行
    if (tmp.x == m)
    tmp.x = tmp.h = 0;
    // 新建输入的宽高
    a[i] = new Pair(nextInt(), nextInt());
    cr[i] = new Triple();
    Pair b = Change(a[i], m - tmp.x);
    // 保存当前的位置
    cr[i].x = tmp.x + b.x;
    cr[i].h = Math.max(tmp.h, b.y);
    cr[i].y = cr[i].h + tmp.y - tmp.h;
  }
  Triple A[] = new Triple[m];
  Triple B[] = new Triple[m];
  for (int i = 0; i < m; i++) {
    A[i] = new Triple();
    B[i] = new Triple();
  }
  int ans = cr[n].y;
  // 把每一个都尝试一下
  for (int i = n; i >= 1; i--) {
    // 处理删除第i块的答案ah
    Triple pre = cr[i - 1];
    int ah;
    if (pre.x == m) {
    ah = pre.y + B[0].y;
    } else {
    ah = pre.y - pre.h + B[pre.x].y - B[pre.x].h + Math.max(pre.h, B[pre.x].h);
    }
    ans = Math.min(ans, ah);
    // 逆向DP，处理出第i至n块从(0,j)位置开始放置
    for (int j = 0; j < m; j++) {
    Pair b = Change(a[i], m - j);
    Triple tmp;
    // 放完这个我就要换行
    if (j + b.x == m)
      tmp = new Triple(0, B[0].y, 0);
    // 如果不换行，还是这个
    else
      tmp = new Triple(B[j + b.x]);
    A[j].h = Math.max(b.y, tmp.h);
    A[j].y = A[j].h + tmp.y - tmp.h;
    }
    for (int j = 0; j < m; j++)
    B[j] = new Triple(A[j]);
  }
  PW.print(ans);
  PW.close();
  }
  // a的x小就返回a，否则返回
  static Pair Change(Pair A, int x) {
  if (A.x <= x)
    return new Pair(A);
  return new Pair(x, (A.y * x + A.x - 1) / A.x);
  }
}
class Pair implements Comparable<Pair> {
  int x, y;
  Pair() {
  }
  Pair(Pair A) {
  x = A.x;
  y = A.y;
  }
  Pair(int x, int y) {
  this.x = x;
  this.y = y;
  }
  @Override
  public int compareTo(Pair A) {
  return x == A.x ? y - A.y : x - A.x;
  }
}
class Triple {
  int x, y, h;
  Triple() {
  }
  Triple(int x, int y, int h) {
  this.x = x;
  this.y = y;
  this.h = h;
  }
  Triple(Triple A) {
  x = A.x;
  y = A.y;
  h = A.h;
  }
  @Override
  public String toString() {
  return String.valueOf(x) + " " + String.valueOf(y) + " " + String.valueOf(h);
  }
}