第八届蓝桥杯省赛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);
  }
}