1
我需要更多的測試用例來顯示正確的答案，但是UVa仍然不接受它。UVA測試用例822
該指令是， 隨着請求收到，他們根據預定的主題列表進行分類。支持人員的每個成員都對這些主題中的一個或多個負責，每個主題都有一個或多個分配給它的支持人員。由於工作人員具有不同的專業知識水平，因此每位工作人員都有一個優先處理的主題清單。工作人員不得在特定區域以外處理請求。
當員工成員可用時，他們根據他們的主題優先級列表從等待請求池中進行選擇。在時間t到達的所有請求都可以在時間t分配。如果同時有兩名工作人員，則計劃優先考慮最近工作最早計劃的人員。如果仍然存在平局，則調度優先權給予其ID號出現在員工輸入列表中較早的人員。在開業時，所有人員都可以處理請求。
輸入包含許多場景。每個場景都以請求主題的數量開始，一個不大於20的正整數。隨後是每個主題的描述。每個描述由五個整數值組成：唯一的主題標識符，該主題的請求數量，接收到該主題的第一個請求之前的已用時間，服務請求所需的時間以及連續請求之間的時間。除了這些值的第三個以外，所有值都是正整數。直到第一個請求的經過時間可能爲零。在此之後，給出了人員的數量。這將是一個不超過5的正整數。最後，以三個或更多正整數值的形式給出每個人的描述：該人的唯一識別號碼，該人覆蓋的主題的數量以及從那個人的最高優先級到最低優先級安排的主題標識符的列表。最後一個場景之後是零。
輸出是每個場景總分鐘的總和。
這裏是我的程序運行的例子： 輸入：
3
128 20 0 5 10
134 25 5 6 7
153 30 10 4 5
4
10 2 128 134
11 1 134
12 2 128 153
13 1 153
1
128 5 0 1 10
1
11 1 128
0
輸出：
Scenario 1: All requests are serviced within 195 minutes.
Scenario 2: All requests are serviced within 41 minutes.
我的代碼：
import java.util.Scanner;
import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
class Main {
public static void main(String[] args) {
class RequestSet{//Structure for RequestSets
private int id;
private int qty;
private int firstReq;
private int timeReq;
private int nextReq;
private int sucReq;
private int initialized;
public RequestSet(int id,int qty,int firstReq,int timeReq,int nextReq){
this.id=id;
this.qty=qty;
this.firstReq=firstReq;
this.timeReq=timeReq;
this.nextReq=nextReq;
sucReq=nextReq;
initialized=0;
}
public void decReq(){//Decreases the time attributes
if(firstReq>1)
firstReq-=1;
else if((nextReq!=1) && (firstReq==0 || firstReq==1))
nextReq-=1;
}
public int getInitial(){//Determines if the Request set has already enqueued its first element
return initialized;
}
public void setInitial(){
initialized=1;
}
public void decQty(){//Decreases the requests qty of the Request set(When the set enqueues a request to the spool)
qty--;
}
public void restoreReq(){//Replenishes the time remaining until the next Request
nextReq=sucReq;
}
public int getID(){
return id;
}
public int getQty(){
return qty;
}
public int getFReq(){
return firstReq;
}
public int getTimeReq(){
return timeReq;
}
public int getNReq(){
return nextReq;
}
}//End of Class "Request Set"
class Request{//Structure for a Request
private int topicID;
private int minsNeeded;
public Request(int id, int mins){
topicID = id;
minsNeeded = mins;
}
public int getMins(){
return minsNeeded;
}
public int getId(){
return topicID;
}
}//End of Class "Request"
class Server{//Structure for Agents
private int id;
private int topicsQty;
private ArrayList<Integer> specialty;
private int available;
private int recentJobAgo;
private int occTil;
private int listStanding;
public Server(int id, int qty, int stand){
this.id=id;
topicsQty=qty;
available=1;
specialty = new ArrayList();
occTil=0;
listStanding=stand;
}
public Server(){
}
public int getOcc(){
return occTil;
}
public int getPosition(){//Returns the position of the agent in the input list(Agent which was inputted first)
return listStanding;
}
public int getRecJ(){//Return the time elapsed after the most recent job
return recentJobAgo;
}
public void display(){
int i;
for(i=0;i<topicsQty;i++){
System.out.printf("%d ",specialty.get(i));
}
}
public void progress(){
if(available==1)//if agent is available, the time elapsed after the most recent job is incremented
recentJobAgo+=1;
else if(available==0 && (occTil==1 || occTil==0)){//case wherein an agent finishes a request. "occTil==0"-occupied til 0 mins
available=1;
occTil=0;
}
else//case where in the agent's still occupied, so we decrease the "Occupied Until" attribute
occTil--;
}
public int isAvailable(){
return available;
}
public void occupy(int time){//Agent begins servicing a request
if(time>0){
available=0;
recentJobAgo=0;
occTil=time;
}
}
public void doneReq(){
available=1;
}
public void learnTopics(int topicID){//Gets the input from the 3rd to the nth input, for agents. Priority topics.
int i;
specialty.add(topicID);
}
public int canDo(int id, int i){//returns 1 if the topicID is in the agent's ArrayList of topic names
int result=0;
//for(i=0;i<topicsQty;i++){
if(i<specialty.size())
if(id==specialty.get(i) && available==1){
result=1;
}
//}
return result;
}
}//End of Class "Server"
int topics, servers, i, result, check, rounds=0, minute;
String dump;
ArrayList<Integer> minutes;
Scanner sc = new Scanner(System.in);
int j, k=0;
int topicID, noReqs, bFirst, timeReq, betReqs, set;
//topicID,# of Requests, time before the 1st request, time requirement to process a request, succeeding time between requests
int agentID, lrndTopics, aTopic;
//agentID, # of priority topics, used to hold a topicID
ArrayList<RequestSet> requests;
Server[] agent;//Could have also been an arraylist
Server temp;//for sorting the agents
String input;
Queue<Request> spool = new LinkedList<>();
minutes=new ArrayList();//Used to hold several results. i.e. if the user inputs several scenarios
int firstInput=sc.nextInt();
if(firstInput!=0){
do{
if(k==0)
{
topics=firstInput;
}
else
{
topics=rounds;
}
dump=sc.nextLine();//Filters out "Enter"/"NextLine"
requests = new ArrayList();
for(i=0; i<topics; i++)
{
// input=sc.nextLine();//Gets a string input containing 5 numbers
// StringTokenizer strToken = new StringTokenizer(input);
// topicID=Integer.parseInt((String)strToken.nextElement());//Gets the first number from the input
// noReqs=Integer.parseInt((String)strToken.nextElement());//Gets the 2nd
// bFirst=Integer.parseInt((String)strToken.nextElement());//3rd
// timeReq=Integer.parseInt((String)strToken.nextElement());//4th
// betReqs=Integer.parseInt((String)strToken.nextElement());//5th
// requests.add(new RequestSet(topicID,noReqs,bFirst,timeReq,betReqs));//Adds the request topic into the RequestSet array
//input=sc.nextLine();//Gets a string input containing 5 numbers
//StringTokenizer strToken = new StringTokenizer(input);
topicID=sc.nextInt();//Gets the first number from the input
noReqs=sc.nextInt();//Gets the 2nd
bFirst=sc.nextInt();//3rd
timeReq=sc.nextInt();//4th
betReqs=sc.nextInt();//5th
requests.add(new RequestSet(topicID,noReqs,bFirst,timeReq,betReqs));//Adds the request topic into the RequestSet array
}
servers=sc.nextInt();//Gets the number of Agents
dump=sc.nextLine();//Filters out "Enter"/"NextLine"
agent = new Server[servers];//Creates an array of agents
for(i=0; i<servers; i++)
{
// input=sc.nextLine();//Accepts a line of input
// StringTokenizer strToken = new StringTokenizer(input);
//System.out.println("agent section");
agentID=sc.nextInt();//Gets the first input
lrndTopics=sc.nextInt();//Gets the 2nd input
agent[i] = new Server(agentID, lrndTopics,i);//Creates an agent in the array
for(j=0;j<lrndTopics; j++)//Gets the priority list of topics, loops n times based on the 2nd input
{
aTopic=sc.nextInt();//Gets the 3rd input until the nth input
agent[i].learnTopics(aTopic);//calls a function that adds the topic into the agent's priority list.
}
}//Gets inputs for the agent set
set=0;//prevents the "minute" variable from increasing at the beginning
minute=0;
//Request processing section
//PROCESSING PART
do{
if(set==1)
minute++;
for(i=0;i<topics;i++)//Checks if a request set is able to add a request into the Queue
{
if((requests.get(i).getFReq()==0 || requests.get(i).getFReq()==1) && requests.get(i).getInitial()==0)
{
spool.add(new Request(requests.get(i).getID(),requests.get(i).getTimeReq()));
requests.get(i).decQty();
requests.get(i).restoreReq();
requests.get(i).setInitial();
}
else if(requests.get(i).getInitial()==1 && (requests.get(i).getNReq()==1) && requests.get(i).getQty()>0)
{
spool.add(new Request(requests.get(i).getID(),requests.get(i).getTimeReq()));
requests.get(i).decQty();
requests.get(i).restoreReq();
}
else
{
requests.get(i).decReq();
}
}
//Sorts the agents according to their idle time. Most idle places first
// for(i=0;i< (servers-1);i++)
// {
// for(j=0;j< servers-i-1;j++)
// if(agent[j].getRecJ()<agent[j+1].getRecJ())
// {
// temp=agent[j];
// agent[j]=agent[j+1];
// agent[j+1]=temp;
// }
// }
//Swaps agents when they have equal idle time. The agent that was inputted first places first
for(i=0;i< servers-1;i++)
{
if(agent[i].getRecJ()==agent[i+1].getRecJ()){
if(agent[i].getPosition()>agent[i+1].getPosition()){
temp=agent[i];
agent[i]=agent[i+1];
agent[i+1]=temp;
}
}
}
//Decreases all the time attributes of all the agents
for(i=0;i<servers;i++)
{
agent[i].progress();
}
//Checks all agents if they're qualified to service a topic
for(j=0;j<topics;j++)
{
for(i=0;i<servers;i++)
{
if(spool.peek()!=null)
{
if(agent[i].canDo(spool.peek().getId(),j)==1)
{
agent[i].occupy(spool.peek().getMins());
spool.remove();
}
}
}
}
set=1;
check=0;
result=0;
//Checks all the requests sets' number of remaining topics
for(j=0;j<topics;j++)
{
if(requests.get(j).getQty()!=0)
check=1;
}
//Checks if all the agents are occupied
for(i=0;i<servers;i++)
{
if(agent[i].isAvailable()==0)
result=1;
}
if(check==0 && result==1)//if all request sets are empty, check if an agent is still servicing a topic
check=1;
// System.out.println(requests.get(0).getQty()+" QTY");
// System.out.println(agent[0].getOcc()+" OCCTIL");
}while(check==1);//End of PROCESSING PART
minutes.add(minute);//Adds the result into the results array
rounds=sc.nextInt();//If '0' is inputted, the program ends, otherwise, it will be stored into the "topics" variable
if(rounds!=0)
k++;
for(i=topics-1;i>=0;i--)//Removes all the request sets from the requests array, to prepare for a next scenario
requests.remove(i);
}while(rounds!=0);
}
//Displays all the results
for(i=0;i<minutes.size();i++)
System.out.println("Scenario "+(i+1)+": All requests are serviced within "+minutes.get(i)+" minutes.");
}
}