pat天梯赛考试座位号,此题运行超时

墨染白筝
  • 147

pat的一个题
图片描述

提示运行超时了。这个题我能想到的存储方式就是二维数组。知识储备还是太少= =
网上能找到的都是C++用结构体做的,找不到java的

import java.util.Scanner;

public class L1_005 {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int sum = in.nextInt();
        String[][] examnumber = new String[sum][3];
        for(int i = 0;i<sum;i++){
            for(int j = 0;j<3;j++){
                examnumber[i][j] = in.next();
            }
        }
        int textnumber = in.nextInt();
        String[] s = new String[textnumber];
        for(int i = 0;i<textnumber;i++){
            s[i] = in.next();
        }
        for(int i = 0;i<textnumber;i++){
            for(int a = 0;a<sum;a++){
                    if(s[i].equals(examnumber[a][1])){
                        System.out.println(examnumber[a][0]+" "+examnumber[a][2]);
                    }
            }
        }
    }

}

pat此题地址:
https://www.patest.cn/contest...
java做,有别的办法做吗?还有运行超时是输入的地方超时了,还是查找匹配地方运行超时了呢?

回复
阅读 3.9k
6 个回答

用java的Scanner只读入数据就超时了(读入数据见下),真心给跪

import java.io.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    int sum = in.nextInt();
    String str, test, exam;
    for (int i = 0; i < sum; i++) {
      str = in.next();
      test = in.next();
      exam = in.next();
    }
    int textnumber = in.nextInt();
    for (int i = 0; i < textnumber; ++i) {
      test = in.next();
    }
  }
}

在C++11出现之前他们到底是怎么写代码的……

#include <iostream>
#include <string>
#include <map>

std::map<std::string, std::pair<std::string, std::string> > map;

int main(int argc, char *argv[]) {
  int sum;
  std::string str, test, exam;

  std::cin >> sum;

  for (int i = 0; i < sum; i++) {
    std::cin >> str >> test >> exam;
    map.insert(std::make_pair(test, std::make_pair(str, exam)));
  }

  std::cin >> sum;

  for (int i = 0; i < sum; i++) {
    std::cin >> test;
    std::map<std::string, std::pair<std::string, std::string> >::iterator pair = map.find(test);
    std::cout << pair->second.first << " " << pair->second.second << std::endl;
  }

  return 0;
}

这道题应该是用java会超时吧!我试着按照c++的思路写,但是一直超时。。感觉应该是java的读取时间太慢了吧。

import java.io.*;
import java.util.*;

public class Main{

    public static void main(String[] args) {
       Scanner in = new Scanner (System.in);
        int sum = in.nextInt();
        String[] str = new String[1005];
        int[][] examnumber = new int[1005][2];
        for(int i = 0;i<sum;i++){
                str[i]= in.next();
                examnumber[i][0] = in.nextInt();
                examnumber[i][1] = in.nextInt();
        }
        int textnumber = in.nextInt();
        int tmp;  
      for(int i = 0;i<textnumber;++i){
            tmp = in.nextInt();
              for(int a = 0;a<sum;++a){
                    if(tmp == examnumber[a][0]){
                      System.out.println(str[a]+" "+examnumber[a][1]);
                      break;
                    }
            }
        }
    }
}

搜到一些说法。http://www.zhihu.com/question...发现一个人的博客,其它pat题都是用java,这道用的c++,也在说这道题用java会超时。。。= = 附上这个人的博客链接http://blog.csdn.net/qq_34594...

pat之前学数据结构玩过半个学期+一个暑假, java真的是写到吐血都过不了.... 我记着ac 这儿的题最好用c, C++有可能都超时, 我感觉这个题用单词查找树比较好吧. 算法渣, 轻喷

个人觉得除了输入输出,已经优化到极致了,复杂度O(n+m),中间两组仍然过不了。
全部都用string数组的原因是,在c++读字符串比较快。。。。java不清楚,但感觉会快一点。

import java.util.Scanner;

public class Main {

  public static void main(String[] args) {
    int n;
    Scanner scanner = new Scanner(System.in);
    n = scanner.nextInt();
    String[] stringnu = new String[n];
    String[] stringv = new String[n];
    String ts;
    int tmp;
    while (n-- != 0) {
      ts = scanner.next();
      tmp = scanner.nextInt();
      --tmp;
      stringnu[tmp] = ts;
      stringv[tmp] = scanner.next();
    }
    n = scanner.nextInt();
    while (n-- != 0) {
      tmp = scanner.nextInt();
      --tmp;
      System.out.println(stringnu[tmp] + " " + stringv[tmp]);
    }
    scanner.close();
  }
}
sys_
  • 2
新手上路,请多包涵
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏