首页 > 专题系列 > Java解POJ > POJ 3483 Loan Scheduling [解题报告] Java
2013
11-12

POJ 3483 Loan Scheduling [解题报告] Java

Loan Scheduling

问题描述 :

The North Pole Beach Bank has to decide upon a set App of mortgage applications. Each application aApp has an acceptance deadline da, ie. the required loan must be paid at a time ta, 0≤tada. If the application is accepted the Bank gets a profit pa. Time is measured in integral units starting from the conventional time origin 0, when the Bank decides upon all the App applications. Moreover, the Bank can pay a maximum number of L loans at any given time. The Bank policy if focussed solely on profit: it accepts a subset SApp of applications that maximizes the profit . The problem is to compute the maximum profit the Bank can get from the given set App of mortgage applications.

For example, consider that L=1, App={a,b,c,d}, (pa,da)=(4,2), (pb,db)=(1,0), (pc,dc)=(2,0), and (pd,dd)=(3,1). The table below shows all possible sets of accepted mortgage applications and the scheduling of the loan payments. The highest profit is 9 and corresponds to the set {c,d,a}. The loan requested by the application c is paid at time 0, the loan corresponding to d is paid at time 1, and, finally, the loan of a is paid at time 2.

Time Sets of accepted applications and loan scheduling
0 a b c d b c b b c c d d a b c
1 a d d d a a a d d d d
2 a a a a a a a
Profit 4 4 4 1 2 3 3 4 5 5 5 6 6 7 7 7 7 8 9

输入:

Write a program that reads sets of data from an input text file. Each data set corresponds to a set of mortgage applications and starts with two integers: 0≤N≤10000 that shows the number of applications in the set, and 0≤L≤100 which shows the maximum number of loans the Bank can pay at any given time. Follow N pairs of integers pi di, i=1..N, that specify the profit 0≤pi≤10000 and the deadline 0≤di≤10000 of the application i. Input data are separated by white spaces, are correct, and terminate with an end of file.

输出:

For each data set the program computes the maximum profit the Bank can get from the accepted mortgage applications corresponding to that data set. The result is printed on standard output from the beginning of a line. There must be no empty lines on output. An example of input/output is shown below.

样例输入:

4 1     4 2  1 0   2 0    3 1

7 2
200 1   200 1   100 0   1000 2    80 1
50 20   500 1

0 100

1 0     4 1000

样例输出:

9
2050
0
0

解题代码:

//* @author:alpc12
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.Arrays;
import java.util.Scanner;


public class Main {

    public static void main(String[] args) throws FileNotFoundException {
        new Main().run();
    }
    
    int[] f;
    int[] dp;
    
    int Root(int x) {
        if(f[x] == x) 
            return x;
        return f[x] = Root(f[x]);
    }
    
    private class Node implements Comparable {
        int p, d;

        public Node() {
            super();
        }

        public Node(int p, int d) {
            super();
            this.p = p;
            this.d = d;
        }

        public int compareTo(Object arg0) {
            return -(p-((Node)arg0).p);
        }
    }

    private void run() throws FileNotFoundException {
         Scanner cin = new Scanner(System.in);
 
        while(cin.hasNextInt()) {
            int n = cin.nextInt();
            int l = cin.nextInt();
 
            Node p[] = new Node[n];
            int max = 0;
            for(int i = 0; i < n; ++i) {
                p[i] = new Node(cin.nextInt(), cin.nextInt());
                p[i].d++;
                p[i].d *= l;
                max = Math.max(max, p[i].d);
            }
            max++;
            Arrays.sort(p);

            f = new int[max];
            for(int i = 0; i < max; ++i) f[i] = i;
            
            int sum = 0;
            for(int i = 0; i < n; ++i) {
                int x = p[i].d;
 
                int r = Root(x);
                if(r != 0) {
                    f[r] = r-1;
                    sum += p[i].p;
 
                }
            }
            System.out.println(sum);
            
        }
        
    }

}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。