请教一下我这个解法怎么不对了--UVa 11418 Clever Naming Patterns

题是这里的：https://uva.onlinejudge.org/inde ... roblem&problem=2413问的是 给一系列词组，仅从每组中按字母表顺序取一个词，比如
有这三个组：
Dog Cat Big
Better
Answer Call


需要取3个词，A,B,C, 开头，每组取一词。第二组的B必须用上，第三组的A必须用上，剩余的第一组就必须取Cat了:
Answer
Better
Cat

很弱很渣所以直接写了一个算是暴力的解法，用linkedlist存所有词组的String[26] array，(不存超范围的词），linear search每次取出仅有一个元素的array entry, 然后删掉其他array的同字母entry...UVa online judge 说 "wrong answer", tim = 0.242 （上限是一秒）. 大神们来看下 或者提示提示更好解...

1. import java.util.Arrays;
   
2. import java.util.Scanner;
   
3. 
   
4. public class Main {
   
5.     public static void main(String[] args) {
   
6.         Scanner input = new Scanner(System.in);
   
7. 
   
8.         int cases = Integer.parseInt(input.nextLine());
   
9. 
   
10.         for (int c = 0; c < cases; c++) // for all cases
    
11.         {
    
12.             LinkedList listops = new LinkedList();
    
13.             int num = input.nextInt();
    
14.             input.nextLine();
    
15.             // num problems and num lines of options
    
16.             for (int n = 0; n < num; n++) {
    
17.                 container perLine = new container();
    
18.                 int numwords = input.nextInt(); // num options per line
    
19.                 for (int word = 0; word < numwords; word++) {
    
20.                     String entry = input.next();
    
21.                     perLine.add(entry, num);
    
22.                 }
    
23.                 listops.insertAtHead(perLine);
    
24.             }
    
25.             // now we have a linked list of containers of words (sorted by
    
26.             // container size)
    
27.             // now "pop them"
    
28.             System.out.println("Case #" + (c + 1));
    
29.             listops.printResults(num);
    
30.             input.nextLine(); // fire a blank nextLine call after
    
31.             // nextInt to get rid of newline left in buffer
    
32.         }
    
33.         input.close();
    
34.         System.exit(0);
    
35.     }
    
36. 
    
37. }
    
38. 
    
39. class container { // custom container class (node)
    
40.     private String[] ray;
    
41.     public int count;
    
42.     public container next;
    
43. 
    
44.     container() {
    
45.         ray = new String[26];
    
46.         next = null;
    
47.     }
    
48. 
    
49.     container(container n) {
    
50.         ray = new String[26];
    
51.         next = n;
    
52.     }
    
53. 
    
54.     void add(String word, int size) {
    
55.         String lower = word.toLowerCase();
    
56.         int first = lower.charAt(0); // first letter
    
57.         // e.g. if size=3, we want a (97), b(98), or c(99), that is >=97,
    
58.         // <=99=(96+size)
    
59.         if (first > (96 + size) || first < 97)
    
60.             return; // simply skip;
    
61.         ray[first - 97] = word;
    
62.         count++;
    
63.     }
    
64. 
    
65.     void del(String word) {
    
66.         int idx = word.toLowerCase().charAt(0) - 97;
    
67.         if (ray[idx] != null) {
    
68.             ray[idx] = null;
    
69.             count--;
    
70.         }
    
71. 
    
72.     }
    
73. 
    
74.     String get() { // return the only String entry
    
75. 
    
76.         int k = 0;
    
77.         while (ray[k] == null)
    
78.             k++;
    
79.         return ray[k];
    
80.     }
    
81. }
    
82. 
    
83. class LinkedList {
    
84.     public container head;
    
85. 
    
86.     LinkedList() {
    
87.         head = null;
    
88.     }
    
89. 
    
90.     void insertAtHead(container ct) {
    
91.         ct.next = head;
    
92.         head = ct;
    
93.     }
    
94. 
    
95.     String getSingleTon() {
    
96.         container ptr = head;
    
97.         while (ptr != null) {
    
98.             if (ptr.count == 1)
    
99.                 return ptr.get();
    
100.             ptr = ptr.next;
     
101.         }
     
102.         return null;
     
103.     }
     
104. 
     
105.     void deleteEntryReorder(String entry) {
     
106.         container ptr = head;
     
107.         while (ptr != null) {
     
108.             ptr.del(entry);
     
109.             ptr = ptr.next;
     
110.         }
     
111.     }
     
112. 
     
113.     void printResults(int size) {
     
114.         String[] res = new String[size];
     
115.         for (int i = 0; i < size; i++) {
     
116.             res[i] = getSingleTon();
     
117.             deleteEntryReorder(res[i]);
     
118.         }
     
119.         Arrays.sort(res);
     
120.         for (int j = 0; j < res.length; j++)
     
121.             System.out.println(res[j].substring(0, 1).toUpperCase()
     
122.                     + res[j].substring(1).toLowerCase());
     
123.     }
     
124. 
     
125. }
     

复制代码

怎么保证会存在仅有一个元素的list呢？

gp89757 发表于 2015-9-23 16:05
怎么保证会存在仅有一个元素的list呢？

举个例子：
假如我们需要3个词，这样就有三行input:
s1
s2
s3
根据题设，s1, s2, s3中有且仅有unique的三个词以A, B, C开头的
对于每一行input, 我仅读入以A, B, or C 开头的单词，其余的(D, E, F, etc.) 都扔掉
既然input行数跟需要的单词数相等，每一行只能提供A,B,C开头的一个词；既然这个题说每个case答案都是唯一的，那么必须有一行仅提供一个词，比如s2 提供A词；把s1, s3的可能存在的A词删掉后，这剩余的两行必须uniquely提供B和C开头词，那么必须s1或s3中有单独的B词或C词...

我自己的还有UVa给的那个test input都给出正确答案啊。。。UVa光说个"wrong answer"并无卵...

这个题可能还是要用bipartite matching 来做. 具体还没想好

tommy410303 发表于 2015-9-24 10:22
举个例子：
假如我们需要3个词，这样就有三行input:
s1

我觉得你是对的 java的看不懂 之前理解错你的意思了

Ok谢谢 我再研究研究