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無法解決 - 記錄保存

回答

相關問題