PAT甲级1001A+BFormat20分

题目简介

Calculate a&＃43;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).

输入信息

Each input file contains one test case. Each case contains a pair of integers a and b where ​​ -10^6 <&＃61; a,b <&＃61; 10^6 The numbers are separated by a space.

输出信息

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.

输入样例

-1000000 9

输出样例

-999,991

分析

给定两个数a和b&＃xff0c;计算他们的和&＃xff0c;并每三个添加分隔符&＃xff08;在千分位添加分隔符&＃xff09;
由于都是在int范围内&＃xff0c;所以不用考虑溢出的问题。&＃xff08;最大2×10^6&＃xff09;

首先有一个最简单的方法&＃xff0c;就是掏出Java里面一个非常有用的类——DecimalFormat
&＃xff08;PS&＃xff1a;在PAT考试里面&＃xff0c;对于时间限制要求不高的20分题目&＃xff0c;用Java往往可以很快秒杀。只要用好String、BigInteger、DecimalFormat等类&＃xff09;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.text.DecimalFormat;
import java.util.StringTokenizer;public class Main {static final int BUFFER_SIZE &＃61; 8192 * 25;static BufferedReader br;static StringTokenizer tokenizer;static void initInput(InputStream in) throws Exception {br &＃61; new BufferedReader(new InputStreamReader(in), BUFFER_SIZE);tokenizer &＃61; new StringTokenizer("");}static String next() throws Exception {while (!tokenizer.hasMoreTokens()) {tokenizer &＃61; new StringTokenizer(br.readLine());}return tokenizer.nextToken();}static int nextInt() throws Exception {return Integer.parseInt(next());}static PrintWriter pw;public static void main(String[] args) throws Exception {initInput(System.in);pw &＃61; new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out), BUFFER_SIZE));/*正式代码开始*/int a &＃61; nextInt(),b&＃61;nextInt();int c &＃61; a&＃43;b;DecimalFormat df &＃61; new DecimalFormat("#,###");//如果要求按四位分割&＃xff0c;就改为#,####即可pw.println(df.format(c));/*结束*/pw.flush();}
}

如图&＃xff0c;核心代码只有四行。&＃xff08;关于为什么IO要这么写的说明附在文后&＃xff0c;并会给出一个模版&＃xff09;

不出意料&＃xff0c;耗时和内存都很高&＃xff0c;这是用Java写PAT的常态&＃xff08;Python耗时都比Java强。但是不妨碍好用~过了就行&＃xff09;

正常考试我们1分钟拿到分就跑了&＃xff0c;但是作为学习阶段应该再认真思考一下到底应该怎么做。
对于一个数 1234567890 &＃xff08;求和之后&＃xff09;&＃xff0c;应该表示为1,234,567,890
如果将这个数转化为字符串&＃xff0c;其每一位的字符与下标对应关系如下&＃xff1a;
0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
可以看出&＃xff0c;在打印str[0] 、str[3]、str[6]字符之后需要打印一个逗号。
通过观察规律&＃xff0c;设下标为i&＃xff0c;则满足条件 (i&＃43;1)%3&＃61;&＃61;len%3 时需要打印一个逗号。如果 i 是最后一位&＃xff08;即 i&＃61;&＃61;len-1 &＃xff09;不需要打印。如果是负数&＃xff0c;跳过即可&＃xff0c;同样符合这个规律。
如&＃xff1a; -1234567
0 1 2 3 4 5 6 7

• 1,2 3 4,5 6 7
  在str[1]&＃xff0c;str[4]之后打印逗号。
  &＃xff08;参考 &＃64;柳婼 的思路&＃xff09;
  C&＃43;&＃43;实现如下&＃xff1a;

#include
#include
using namespace std;
int main() {int a, b;scanf("%d %d", &a, &b);string s &＃61; to_string(a &＃43; b);for (int i &＃61; 0; i < s.length(); i&＃43;&＃43;) {printf("%c", s[i]);if (s[i] !&＃61; &＃39;-&＃39; && (i &＃43; 1) % 3 &＃61;&＃61; s.length() % 3 && i !&＃61; s.length() - 1)printf(",");}return 0;
}


&＃xff08;这个耗时就是天差地别了。。。&＃xff09;

附录-关于PAT考试中效率&＃xff08;运行时间的问题&＃xff09;

刚开始的三四十道题我也是采用Java答题&＃xff0c;但是后面部分题目实在是无法通过。&＃xff08;限时300ms以下的题目&＃xff0c;用Java通过几乎 不可能&＃xff09;&＃xff0c;下面对于Java的技巧&＃xff0c;也仅仅是在一定程度上改良&＃xff0c;如果只是自己学着练练题目&＃xff0c;可以用Java写&＃xff0c;但是如果是要参加考试&＃xff0c;请趁早转行。原因在于&＃xff1a;
1、Pat官方解释&＃xff0c;呵呵&＃xff0c;就这样。
2、PTA的判题系统里Java相关的编译程序已经许久 没有维护&＃xff0c;Java虚拟机的启动时间也被算在程序运行时间内。
一、如果采用Java答题
Java属于先编译后解释的语言&＃xff0c;虽然由.java编译成.class文件的时间不算在内&＃xff0c;但是Java虚拟机启动&＃xff08;长达50ms&＃43;&＃xff09;的时间会被算在里面。如果采用了低效的IO方法&＃xff0c;效果会更差。相比而言&＃xff0c;纯解释型语言&＃xff08;如Python&＃xff09;&＃xff0c;反倒更快&＃xff08;相比较而言&＃xff09;。
下面的几个提升运行速度的方法&＃xff0c;实际效果依次减弱。

• 使用C&＃43;&＃43;改写。
• 停止使用Scanner读入&＃xff0c;改用封装过的Reader类

BufferedReader br &＃61; new BufferedReader(new InputStreamReader(System.in)));


Scanner虽然方便好用&＃xff0c;但是效率极差&＃xff0c;参见
Fast Input for Java
某使用Java打国际acm选手做的实验

• 使用StringTokenizer代替String.parse&＃xff0c;StringTokenizer的效率会比String.parse高好几倍。
• 在上一条中的链接里也有解释。
• 停止使用System.in输出&＃xff0c;改用封装过的Writer类。

PrintWriter pw &＃61; new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));


使用BufferedWriter封装转化而来的System.out&＃xff0c;可以提高效率&＃xff0c;再使用PrintWriter封装&＃xff0c;可以方便使用print、printf、println等方法。

• 所有可以静态化的对象尽量静态化&＃xff08;存疑&＃xff09;
  这个做法的由来是GC不会检查并回收在静态域中的对象&＃xff0c;而减少GC的频率则能一定程度提高运行效率&＃xff08;实际上效果非常不明显&＃xff0c; 几乎没有&＃xff09;
  将不用的对象及时置为null也或许能提高一点效率
• 修改BufferedReader、BufferedWriter默认的缓冲区大小&＃xff08;默认值为8192&＃xff0c;我将它增大到原来的25倍&＃xff09;&＃xff0c;以内存换读取效率。
  这也是为什么要写一行&＃xff1a;

static final int BUFFER_SIZE &＃61; 8192 * 25;


忘了是在哪里见过一次别人这么写&＃xff0c;实际 效果存疑&＃xff0c; 可能并无卵用。

综上几条可以得出Java里面最高效的读写模版如下&＃xff1a;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;public class Main{static final int BUFFER_SIZE &＃61; 8192*25;static BufferedReader br;static StringTokenizer tokenizer;static void initInput(InputStream in) throws Exception {br &＃61; new BufferedReader(new InputStreamReader(in), BUFFER_SIZE);tokenizer &＃61; new StringTokenizer("");}static String next() throws Exception{while(!tokenizer.hasMoreTokens()) {tokenizer &＃61; new StringTokenizer(br.readLine());}return tokenizer.nextToken();}static int nextInt() throws Exception {return Integer.parseInt(next());}static double nextDouble() throws Exception{return Double.parseDouble(next());}static PrintWriter pw;public static void main(String[] args) throws Exception {initInput(System.in);pw &＃61; new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out),BUFFER_SIZE));/*在这里插入你的代码*/int i &＃61; nextInt(); //读取一个整数String s &＃61; next(); //读取一个字符串double d &＃61; nextDouble(); //读取一个浮点数pw.flush();}
}

注&＃xff1a;StringTokenizer的默认分隔符是空格和换行&＃xff0c;如果需要其他方式&＃xff0c;还是用next()读取字符串后使用spilt方法比较合适。
二、如果采用C语言答题
改用C&＃43;&＃43;&＃xff0c;没有STL基本上不能活。
三、如果采用C&＃43;&＃43;答题
C&＃43;&＃43;没什么好说的&＃xff0c;一般来说没有大问题&＃xff08;很多时候 &＃xff0c;Java需要采用最优化的算法才能过&＃xff0c;C&＃43;&＃43;甚至暴力就行了&＃xff09;
只有几点需要注意&＃xff1a;

• 尽量采用scanf和printf来读取或输入&＃xff08;有人说cin、cout取消刷新也可&＃xff09;&＃xff0c;特别是在需要读取大量字符串的时候&＃xff0c;scanf的效率提升尤为明显。
• 善用map、set、unordered_map和unordered_set。一般来说&＃xff0c;如果key是int类型都可以用数组代替&＃xff0c;key是string类型时候才用map。但是如果数据量超大&＃xff0c;就要用到unordered_map。&＃xff08;map/set底层是红黑树实现&＃xff0c;能保证一定有序性&＃xff0c;unordered_map/unordered_set底层是哈希表实现&＃xff0c;效率稍高&＃xff0c;但建表需要时间&＃xff09;
  结论是&＃xff1a;
  一般情况下用数组&＃xff0c;只需要key不需要value用set/unordered_set
  key为string时用map。
  数据量大&＃xff08;用map超时&＃xff09;&＃xff0c;不需要有序性时使用unordered_map。使用unordered_map时&＃xff0c;尽量在初始化时就指定好大小&＃xff08;减少哈希表扩容带来的开销&＃xff09;
  需要有序性&＃xff08;排序&＃xff09;时&＃xff0c;使用map。&＃xff08;后面题目会见到&＃xff09;
• 一些小的点&＃xff0c;能用邻接表就不用邻接矩阵&＃xff0c;用stringstream拼接字符串而不是重载的运算符等等
• 使用vector代替普通数组。数组能干的vector都能&＃xff0c;而且更方便。

当然了&＃xff0c;有的时候图方便可以采用一点低效的方法。反正错了还可以再改&＃xff08;PAT考试不罚时&＃xff09;&＃xff08;逃&＃xff09;