网易游戏研发工程师在线笔试第一批日志记录

本文写于 2019年03月10日，距今已超过 1 年，距 2020年07月25日的最后一次修改也已超过 3 个月，部分内容可能已经过时，您可以按需阅读。如果图片无法显示或者下载链接失效，请给我反馈，谢谢！

Visits: 320

0 0 投票数

评分

文字显示

一直在犹豫这道题是贪心还是动态规划，想了很久，觉得贪心是成立的，后来事实证明确实是成立的。

处理方法是，如果当前是字母，那么很简单，这一行放得下就放在这一行，放不下就新开一行，只需要用一个变量记录一下当前这一行占用了多少宽度就行。

如果当前处理的是标点，那么找到标点结束的地方，把这一整段标点作为一个整体考虑，要么全放在当前行的末尾，如果当前行放不下，那么这一整段就要放到下面一行。

由于这一段都是标点，所以不能从中间截断，否则就势必会有出现在行首的标点，因此，没有其他情况需要考虑。

对于能直接放在当前行末尾的，那么直接放上去，如果放不下，就要放下一行，但是下一行的行首不能是标点，这意味着要从当前行取出一个字母放到下一行的行首，由于标点只作为一个整体考虑，因此，当前行最后一个一定是字母，不会是标点，所以直接判断所有标点长度加 1 以后的大小是不是够放下一行。

任何情况下出现放不下，直接给出 impossible。

对于换行符，由于是无条件换行，所以可以在开始的时候就直接以换行符作为 split，每一段分别计算最短行数，累加得到答案。

特别需要注意的是，\n 的转义是 \\\\n，而不是 \\n。（我以为 \ 的转义是 \\，结果交了一次通过 0% 的样例，修改后再交就是 AC）

import java.util.HashSet;
import java.util.Scanner;

/* 共提交 2 次，第 1 次通过 0% 的样例，第 2 次通过 100% 的样例 */

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int ans = 0;
            int x = in.nextInt();
            int y = in.nextInt();
            String[] ss = in.next().split("\\\\n");
            /* 这里是 \\\\n 表示 \n 的转义，不是 \n 或者 \\n */
            try {
                for (String s : ss) {
                    if (s.length()==0)
                        continue;
                    ans += solve(x,y,s);
                }
            } catch (Exception e) {
                System.out.println("impossible");
                continue;
            }
            System.out.println(ans);
        }
        in.close();
    }

    private static int solve(int x, int y, String s) throws Exception {
        final HashSet<Character> SYMBOL = new HashSet<Character>();
        SYMBOL.add(',');
        SYMBOL.add('.');
        SYMBOL.add('!');
        SYMBOL.add('?');
        int len = s.length();
        int index = 0;
        int yy = 0;
        int ret = 0;
        while (index < len) {
            char c = s.charAt(index);
            if (!SYMBOL.contains(c)) {
                if (yy + x <= y) {
                    yy += x;
                } else {
                    ret++;
                    yy = x;
                }
                index++;
            } else {
                int begin = index;
                while (index < len && SYMBOL.contains(s.charAt(index)))
                    index++;
                int end = index;
                if (yy + x * (end - begin) <= y) {
                    yy += x * (end - begin);
                } else if (x * (end - begin + 1) <= y){
                    yy = x * (end - begin + 1);
                    ret++;
                } else {
                    throw new Exception();
                }
            }   
        }   
        return ret + 1;
    }
}

特殊键盘

最短路径。

这道题看出是最短路径以后就非常简单了，由于只有 26 个字母，所以直接无脑 Floyd 跑三重循环。

注意自己到自己的距离是 1，遇到一个 shift 就加 1。或者也可以自己到自己的距离为 0，最后得到的最短路长度加上原始文章的长度（因为每个按键至少按一次）。

计算出最短路径以后，把损坏的按键那一行的点全部置为无穷大。

计算最短路，如果最短路结果为无穷大，则这篇文章不可能被输出。

import java.util.HashSet;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for (int t = 0; t < T; t++) {
            int n = in.nextInt();
            int[][] keyboard = new int[26][26];
            final int INFINITY = 1000;
            for (int i = 0; i < keyboard.length; i++)
                for (int j = 0; j < keyboard[i].length; j++) {
                    if (i == j)
                        keyboard[i][j] = 0;
                    else 
                        keyboard[i][j] = INFINITY;
                }
            for (int i = 0; i < n; i++) {
                int x = in.next().charAt(0) - 'a';
                int y = in.next().charAt(0) - 'a';
                keyboard[x][y] = 1; 
            }
            int m = in.nextInt();
            HashSet<Character> broken = new HashSet<Character>();
            for (int i = 0; i < m; i++) {
                char c = in.next().charAt(0);
                broken.add(c);
            }

            for (int k = 0; k < keyboard.length; k++)
                for (int i = 0; i < keyboard.length; i++)
                    for (int j = 0; j < keyboard.length; j++)
                        if (keyboard[i][j] > keyboard[i][k] + keyboard[k][j])
                            keyboard[i][j] = keyboard[i][k] + keyboard[k][j];

            for (char c : broken) 
                for (int j = 0; j < keyboard.length; j++) 
                    keyboard[c - 'a'][j] = INFINITY;
            String s = in.next();
            int len = s.length();
            int ans = len;
            for (int index = 0; index < len; index++) {
                int c = s.charAt(index) - 'a';
                int who = c;
                for (int i = 0; i < keyboard.length; i++)
                    if (keyboard[i][c] < keyboard[who][c])
                        who = i;
                if (keyboard[who][c] == INFINITY)
                    ans = -1;
                else 
                    ans += keyboard[who][c];
                if (ans == -1)
                    break;
            }
            System.out.println(ans);
        }
        in.close();
    }
}