JAVA - USACO无法解决 - 记录保存

http://www.usaco.org/index.php?page=viewproblem2&cpid=358

我无法找到解决问题的有效途径。我想按字母顺序组织每组奶牛，这会使它们更容易比较。之后，我可以简单地找到模式。但是，我遇到的算法问题是，呈现给我的奶牛群在每个输入中的数量都不相同。我打算将每组奶牛设置为一个字符串，但这显然不起作用，因为组数可能会有所不同。有没有更好的方法来解决这个问题？

来源

2014-12-13 Vonais

您正朝着正确的方向前进。您还可以更进一步 - 在按字母顺序对每个组进行排序后，按字典顺序对所有组进行排序。让我们的例子：

BESSIE ELSIE MATILDA 
FRAN BESSIE INGRID 
BESSIE ELSIE MATILDA 
MATILDA INGRID FRAN 
ELSIE BESSIE MATILDA

你已经建议的第一步之后，这些将成为：

BESSIE ELSIE MATILDA 
BESSIE FRAN INGRID 
BESSIE ELSIE MATILDA 
FRAN INGRID MATILDA 
BESSIE ELSIE MATILDA

然后整个组进行排序：

BESSIE ELSIE MATILDA 
BESSIE ELSIE MATILDA 
BESSIE ELSIE MATILDA 
BESSIE FRAN INGRID 
FRAN INGRID MATILDA

第二步可以通过考虑用于表示组的整个字符串来完成。排序完成后，问题可以通过一次线性传递完成（我将这个传递给你）。

我建议的方法将工作，因为输入相对较小，因此解决方案不会太慢。对于更大的约束条件，您应该使用哈希来完成第二步（在对每个组中的名称进行排序后）。您也可以将这种方法应用于您的问题，但它有点复杂。

来源

2014-12-13 09:04:27

感谢您的回答！但是，对于“考虑用于表示组的整个字符串”的含义，我有点困惑。你的意思是说我会把每一组奶牛存储到一个字符串中吗？ – Vonais 2014-12-14 02:05:40

这种方法可以实现排序，但是您不能*使用它。我不确定是否可以在Java中对一些数组进行排序，但基本上这就是你需要做的。 – 2014-12-14 06:04:13

这是我对这个问题的回答，我希望它有帮助，这是我在比赛中认为的最好的解决方案，它通过了所有的测试案例。

import java.io.*; 
import java.util.*; 
public class records { 

    public static void main(String[] args)throws IOException { 
     BufferedReader bf = new BufferedReader(new FileReader("records.in")); 
     PrintWriter pw = new PrintWriter(new File("records.out")); 
     int n = Integer.parseInt(bf.readLine()); 
     Map<String, Integer> map = new HashMap<String, Integer>(); 

     for(int i = 1; i<=n ;i++){ 
      String str = bf.readLine(); 
      char[] chars = str.toCharArray(); 
      Arrays.sort(chars); 
      String sorted = new String(chars); 

      if(map.containsKey(sorted)){ 
       int count = map.get(sorted); 
       map.put(sorted, count + 1); 
      }else{ 
       map.put(sorted, 1); 
      } 
     } 

     /*for (String name : map.keySet()) { 
      System.out.println(name + ": " + map.get(name)); 
     }*/ 

     List<Integer> c = new ArrayList<Integer>(map.values()); 
     Collections.sort(c); 
     pw.println(c.get(c.size() -1)); 
     pw.close(); 
    } 
}

来源

2014-12-22 03:37:18 rommel

JAVA - USACO无法解决 - 记录保存

回答

相关问题