uva1203 - Argus (排序、优先级队列)

importjava.io.BufferedReader;
importjava.io.InputStreamReader;
importjava.io.FileReader;
importjava.io.IOException;
importjava.util.StringTokenizer;
importjava.util.Arrays;
importjava.util.PriorityQueue;
classMain{
publicstaticfinalbooleanDEBUG=false;  
publicstaticintN=1010;
publicstaticRegister[] instruction=newRegister[N];
publicstaticintn;
staticclassRegisterimplementsComparable<Register>    {
intnum;
intperiod;
intcnt;
publicintcompareTo(Registerother)
        {
if (period!=other.period) returnperiod-other.period;
returnnum-other.num;
        }
    }
staticclassNodeimplementsComparable<Node>    {
intnum;
intv;
publicintcompareTo(Nodeother)
        {
if (v!=other.v) returnv-other.v;
returnnum-other.num;
        }
    }
publicstaticvoidmain(String[] args) throwsIOException    {
BufferedReadercin;
Strings;
intk;
if (DEBUG) {
cin=newBufferedReader(newFileReader("d:\\OJ\\uva_in.txt"));
        } else {
cin=newBufferedReader(newInputStreamReader(System.in));
        }
n=0;
while ((s=cin.readLine()) !=null) {
if ("#".equals(s)) break;
StringTokenizerst=newStringTokenizer(s);
intcnt=0;
instruction[n] =newRegister();
instruction[n].cnt=0;
while (st.hasMoreTokens()) {
Stringtmp=st.nextToken();
if (cnt==1) {
instruction[n].num=Integer.parseInt(tmp);
                } elseif (cnt==2) {
instruction[n].period=Integer.parseInt(tmp);
                }
cnt++;
            }
n++;
        }
s=cin.readLine();
k=Integer.parseInt(s);
Arrays.sort(instruction, 0, n);
intoutputcnt=k;
inti=0;
while (i<k) {
intstart=instruction[0].period*instruction[0].cnt;
intend=start+instruction[0].period;
PriorityQueue<Node>pq=newPriorityQueue<Node>();
for (intj=0; j<n; j++) {
intcur=instruction[j].period* (instruction[j].cnt+1);
if (cur>=start&&cur<=end) {
i++;
Nodetmp=newNode();
tmp.num=instruction[j].num;
tmp.v=cur;
instruction[j].cnt++;
pq.add(tmp);
                }
            }
while (!pq.isEmpty() &&outputcnt>0) {
System.out.println(pq.poll().num);
outputcnt--;
            }
        }
    }
}