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

Question

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做，有别的办法做吗？还有运行超时是输入的地方超时了，还是查找匹配地方运行超时了呢？

Answer 1

用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;
}

Answer 2

这道题应该是用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...

Answer 3

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

Answer 4

个人觉得除了输入输出，已经优化到极致了，复杂度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();
  }
}

Answer 5

我用java写的，改进了一下，没超时
https://blog.csdn.net/qq_3473...

Answer 6

我也是用java。也会超时，刚开始用的是一维数组，以为是数组用得太多了，总遍历时间长。所以后来用了treemap存，也是超时，泪。附代码

import java.util.Map;
import java.util.Scanner;
import java.util.TreeMap;

public class Main24 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        Map<Integer,Integer> one = new TreeMap<Integer, Integer>();
        Map<Integer,String> two = new TreeMap<Integer, String>();
        for(int i =0 ;i<N;i++){
            String a = sc.next();
            int b = sc.nextInt();
            int c = sc.nextInt();
            one.put(b, c);
            two.put(c, a);
        }
        int S = sc.nextInt();
        int[] a = new int[S];
        for(int i=0;i<S;i++){
            a[i] = sc.nextInt();
        }
        
        
        for(int j = 0;j<S;j++){
            System.out.println(two.get(one.get(a[j]))+" "+one.get(a[j]));
        }    
    }
    
}

最后有人告诉我说字符串存着慢，那那个准考证号14位能用long存，然而运行了也没有什么卵用吖，只是运行快了一点点，那两个测试点超时的还是照样超时，有没有网友能反推那两个测试点数据啊，都 不知道为什么会超时，如果改成long型就是把上面代码的String改成long型，运行确实会快那么10ms左右，然而那两个测试点还是破不了