首页 > 专题系列 > Java解POJ > POJ 2698 Servicing DVD Requests [解题报告] Java
2013
11-11

POJ 2698 Servicing DVD Requests [解题报告] Java

Servicing DVD Requests

问题描述 :

You are running a DVD library. Suppose that you have k DVD drives, through which the users can access the contents of the requested DVDs.A DVD drive can only access the content of one DVD at the same time. When a DVD request arrives, if the DVD is already in a DVD drive, then nothing needs to be done. Otherwise, you are supposed to insert the requested DVD into an empty drive. If all k drives are occupied, you have to remove a DVD out of the drive before having the requested DVD inserted into the drive. The objective is to minimize the number of DVD insertions required for serving the whole sequence of requests.

To make things interesting, we assume that you are given the whole sequence x1, x2, . . . , xn in advance. Also, you have to service request xi before servicing xi+1, for each i = 1, 2, . . . , n – 1. You want to carefully plan how to service each request such that the overall number of DVD insertions is minimized. Clearly, the difficulty lies in determining which DVD should be removed from its drive when you receive a request to a DVD not in any drive and all drives are occupied.

For example, let k = 2, and let the sequence of requests be 1, 2, 3, 1, 3, 1, 3. For the first two requests, one can simply put DVDs 1 and 2 into the drives. When the third request (i.e., DVD 3) arrives, you have to either remove DVD 1 or DVD 2 out of its drive so that DVD 3 can be inserted to a drive.

  • If you choose the first option (i.e., removing DVD 1), then the remaining requests (i.e., requests 4-7) need at least one more DVD insertions.
  • If you choose the second option (i.e., removing DVD 2), then the remaining requests (i.e., requests 4-7) need no more DVD insertions.

It is not difficult to verify that the second option results in an optimal way to service the above sequence of requests which needs only three DVD insertions.

输入:

The first line contains the number m of test cases. Each test case starts with a line containing two numbers k and n, where 1 <= k <= 10 is the number of DVD drives and 1 <= n <= 100 is the number of requests. In the following n lines, the i-th line contains the i-th request xi.

输出:

For each test case, your program has to output the minimum number of DVD insertions required to service the whole sequence of requests in one line.

样例输入:

2
2 7
1
2
3
1
3
1
3
3 9
1
2
3
4
1
2
1
2
4

样例输出:

3
4

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
public class Main {
 static final int N = 1000+10;
 static int n,m;
 static int value[] = new int[N];
 public static void main(String []args) throws Exception{
		
  int i,t;
  //Scanner cin = new Scanner(new FileInputStream("input.txt"));
  Scanner cin = new Scanner(System.in);
		
  t = cin.nextInt();
  while(t--!=0){
	n = cin.nextInt();
	m = cin.nextInt();
	for(i=0;i< m;++i)
		value[i] = cin.nextInt();
	System.out.println(solve());
   }
 }

 public static int binary_search(int num[],int key){
  int Min=0,Max=m-1,Mid;
  while(Min+1< Max){
	Mid = (Min+Max)/2;
	if(num[Mid]>key)
		Max = Mid;
	else Min = Mid;
   }
  if(num[Min]==key) return Min;
  return Max;
 }

 public static void make_mapping(){
  int i,j,k;
  int num[] = new int[N];
  int scan[] = new int[N];
		
  for(i=0;i< m;++i) num[i] = value[i];
  Arrays.sort(num,0,m);
  scan[0] = 1;
  for(i=1;i< m;++i){
	if(num[i]==num[i-1]) scan[i] = scan[i-1];
	else scan[i] = scan[i-1]+1;
  }
  for(i=0;i< m;++i){
	value[i] = scan[binary_search(num,value[i])];
  }
 }

 public static int get_last(int cnt,int who){
  int i=cnt+1;
  for(i=cnt+1;i< m;++i)
   if(value[i]==who)
     return i;
   return i;
  }

  public static int solve(){
   make_mapping();
		
   int i,j,k,cnt,last,ans=0,top=0;
   int contain[] = new int [N];
   for(i=0;i< ;++i){
	for(j=0;j< top;++j){
		if(contain[j] == value[i]) break;
	}
	if(j>=top){
		ans++;
		if(top< n){
			contain[top++] = value[i];
		}
		else{
		  cnt = 0;last = get_last(i,contain[0]);
		  for(j=1;j< top;++j){
			k = get_last(i,contain[j]);
			if(k>last){
				cnt = j;
				last = k;
			}
		  }
		  contain[cnt] = value[i];
		}
	}
   }
   return ans;
  }

}

  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?