程序来源:来自我同学在做蓝桥杯的爬树的甲壳虫问题,问题是这样的有一只甲壳虫想要爬上一颗高度为n的树,它一开始位于树根高度为0,当它尝试从高度i-1爬到高度为i的位置时有Pi的概率会掉回树根, 求它从树根爬到树顶时, 经过的时间的期望值是多少。他的程序在大量的输入数据时,运行时间会不通过。
他的程序如下:
点击查看代码
import java.util.Scanner;
public class Main {
static long qqpow(long num,long pow,long mod){
long res=1;
while (pow!=0){
if(pow%2==1){
res=res*num;
}
num*=num;
res%=mod;
num%=mod;
pow>>=1;
}
return res;
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
long sum=0;
long mod=998244353l;
for (long i = 0; i < n; i++) {
long a=sc.nextInt();
long b=sc.nextInt();
sum=((sum+1)%mod*(b%mod))%mod;
sum*=qqpow(b-a,mod-2,mod);
sum%=mod;
}
System.out.println(sum);
}
}
这里没有大量数据,进行演示,所以只简单的说明了,程序输入和输出结果的正确。
但是代码结构基本相同的c语言却不会超时,搜索过资料后发现是用Scanner输入的问题,Scanner输入是调用的api,所以时间会比c语言的直接输入浪费更多的时间,所以结局的办法就是用Streamtokenizer读取字符串,这个适用于超大规模整数型数据的读取,能缩短程序的时间,大大提高了程序的性能。
修改后的代码如下:
点击查看代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
static long qqpow(long num,long pow,long mod){
long res=1;
while (pow!=0){
if((pow&1)==1){
res*=num;
}
num*=num;
num%=mod;
res%=mod;
pow>>=1;
}
return res;
}
public static void main(String[] args) throws Exception {
long mod=998244353l;
long sum=0;
StreamTokenizer in=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int n=(int)in.nval;
while (n-->0){
in.nextToken();
int a=(int) in.nval;
in.nextToken();
int b=(int)in.nval;
sum=((sum+1)%mod*b%mod)%mod;
sum*=qqpow(b-a,mod-2,mod);
sum%=mod;
}
System.out.println(sum);
}
}
最终,成功的解决了超大量数据输入的超时问题,我也体会到了,Java语言比c语言虽然有更多写好的方法可以直接用,但是在算法的运行速度上,是不如c语言快的,也了解了Scanner输入的弊端,只能用于小规模的数据输入,大规模的数据输入,还得用Streamtokenizer.还有在streamtokenizer的输入,要先把数据静态化,才能正常读取。
标签:甲壳虫,res,sum,long,num,3398620,爬树,优化,mod From: https://www.cnblogs.com/one111/p/18045919