PAT 甲级刷题实录——1001

前言

先说个挺不好意思的事，小弟我脑子一热，考研报了浙大。更不好意思的是，自己竟然还报有着能进复试的想法。浙大复试需要上机考试，基本上考试内容和 PAT 考试差不多，所以现在就得开始刷题准备。也不管能不能进复试吧，就算没进复试，去找工作的话练练算法总是有好处的，大学前三年确实没有怎么太注重算法和编码的练习，现在也该补一补。

因为我前三年半没怎么刷过算法题，所以我的基础是很差的。也不怕大家笑话，我就从最简单的题开始一道一道练习。那么今天练习的就是甲级第一题。

原题

Calculate a+b and output the sum in standard format -- that is, the digits must be separated into groups of three by commas (unless there are less than four digits).

Input Specification:

Each input file contains one test case. Each case contains a pair of integers a and b where −10^​6​​≤a,b≤10​^6​​. The numbers are separated by a space.

Output Specification:

For each test case, you should output the sum of a and b in one line. The sum must be written in the standard format.

Sample Input:

-1000000 9

Sample Output:

-999,991

解析

这题乍一看很简单，就是输出两个数的和，但是有个比较复杂的地方，就是每隔千位得加上逗号，变成西方打印的数字形式。说句题外话，这种写法完全就只是为了西方人的方便而考虑的，因为他们是以千为基本单位来读较大的数的，比如 thousand（千）, millon（百万）, billon（十亿）。而中国人则是以万为基本单位来读较大的数的，比如万，亿，兆，这样的写法反而会带来不方便。但没办法，题目里要求这么做，那就只能这么做了。

解法

PAT 考试理论上是可以用各种语言写程序的（抱着我的 Java 摩拳擦掌中）。不过我刚刚看了一下，用 C 语言和 C++ 语言之外的其他语言基本上就是作死，因为速度太慢了（啊，我最爱的 Java）。甚至还有下面这种恐怖的说法：

但我还是不死心，想看看用 Java 写到底是怎么样的效果，之后再用 C 语言或者 C++ 重写一遍对比一下。

这道题我的思路是这样的：把相加的结果转换为字符数组，之后逐个输出数字，当数组长度和输出下标的差减 1 能够整除 3 的时候，就输出逗号。

Java 代码如下：

import java.io.*;
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String st=br.readLine();
		String[] nums=st.split(" ");
		int a=Integer.parseInt(nums[0]);
		int b=Integer.parseInt(nums[1]);
		int c=a+b;
		String str=String.valueOf(c);
		int n=str.length();
		for(int i=0;i<n;i++) {
			System.out.print(str.charAt(i));
			if(c<0&&i!=n-1&&(n-i-1)%3==0&&i!=0) {
				System.out.print(',');
			}
			if(c>0&&(n-i-1)%3==0&&i!=n-1) {
				System.out.print(',');
			}
		}
	}

}

因为老师说别用 Scanner，所以我都不敢用 Scanner 而是换成了 BufferedReader。应该说 Java 要是不用 Scanner，输入特别麻烦，因为 BufferedReader 一次只能读一行，所以我在读完一行之后还得再用 split 方法把参数分割开。特别要注意的是当两数之和为负数的情况，此时若 i==0，则不能输出逗号，否则会输出-,999,999 这样的数字。

这段程序是能够通过测试的，执行情况如图所示：

因为我也没什么做在线算法题的经验，也不知道这个运行效率算什么水平（后来才发现完全不行）。我又尝试用 C++ 写了一遍，代码如下：

#include <iostream>
#include <string>
using namespace std;

int main()
{
    int a,b,c,n;
    cin>>a>>b;
    c=a+b;
    string str=to_string(c);
    n=str.size();
    for(int i=0;i<n;i++){
        cout<<str[i];
        if(c<0&&i!=n-1&&(n-i-1)%3==0&&i!=0) {
            cout<<',';
        }
        if(c>0&&(n-i-1)%3==0&&i!=n-1) {
            cout<<',';
        }

    }
    return 0;
}

这段代码的运行结果如图：

可以看到效率和 Java 相比完全就是一个天上，一个地下，差距也太大了吧。看来以后还是得用 C++ 来做题。

歪门邪道

网上看到一个自己啥也不用干，只要调用 Java 包装好的方法的做法，也把代码贴在这里：

import java.text.DecimalFormat;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner in = new Scanner(System.in);
		DecimalFormat df = new DecimalFormat("#,###");
	        while (in.hasNextInt()) {
            		int a = in.nextInt();
            		int b = in.nextInt();
            		System.out.println(df.format(a+b));
        	}
    	}
}

这个运行效率就更低了，如图：