首页 > 专题系列 > Java解POJ > POJ 1456 Supermarket [解题报告] Java
2013
11-09

POJ 1456 Supermarket [解题报告] Java

Supermarket

问题描述 :

A supermarket has a set Prod of products on sale. It earns a profit px for each product x∈Prod sold by a deadline dx that is measured as an integral number of time units starting from the moment the sale begins. Each product takes precisely one unit of time for being sold. A selling schedule is an ordered subset of products Sell ≤ Prod such that the selling of each product x∈Sell, according to the ordering of Sell, completes before the deadline dx or just when dx expires. The profit of the selling schedule is Profit(Sell)=Σx∈Sellpx. An optimal selling schedule is a schedule with a maximum profit.

For example, consider the products Prod={a,b,c,d} with (pa,da)=(50,2), (pb,db)=(10,1), (pc,dc)=(20,2), and (pd,dd)=(30,1). The possible selling schedules are listed in table 1. For instance, the schedule Sell={d,a} shows that the selling of product d starts at time 0 and ends at time 1, while the selling of product a starts at time 1 and ends at time 2. Each of these products is sold by its deadline. Sell is the optimal schedule and its profit is 80.



Write a program that reads sets of products from an input text file and computes the profit of an optimal selling schedule for each set of products.

输入:

A set of products starts with an integer 0 <= n <= 10000, which is the number of products in the set, and continues with n pairs pi di of integers, 1 <= pi <= 10000 and 1 <= di <= 10000, that designate the profit and the selling deadline of the i-th product. White spaces can occur freely in input. Input data terminate with an end of file and are guaranteed correct.

输出:

For each set of products, the program prints on the standard output the profit of an optimal selling schedule for the set. Each result is printed from the beginning of a separate line.

样例输入:

4  50 2  10 1   20 2   30 1

7  20 1   2 1   10 3  100 2   8 2
   5 20  50 10

样例输出:

80
185

温馨提示:

The sample input contains two product sets. The first set encodes the products from table 1. The second set is for 7 products. The profit of an optimal schedule for these products is 185.

解题代码:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
	private static int[] sell;
	private static Node node;
 	public static boolean isSell(int d){

         if (sell[d] == 0) {
        	 sell[d] = d;
             return true;
         }  else{
        	 for(int i = d-1 ; i >= 1 ; i--){
        		 if(sell[i] == 0){
        			 sell[i] = d;
              		 return true;
        		 }
        	 }
         }
         return false;
	}
	
	public static int getProfix(List l , int n) {
	    int sum = 0;
	    sell = new int[n+1];
        for(int i = l.size()-1 ; i >=0 ; i--){
        	int d = l.get(i).getD();
        	if(isSell(d)){	
               sum = sum + l.get(i).getP();
        	}
        }
		return sum;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while (sc.hasNextInt()) {

			int n = sc.nextInt();
			List< Node> l = new ArrayList ();
			int max = 0;
			for(int i = 0 ;i < n ;i++){
				Main m = new Main();
				Main.node = m.new Node();
				int p = sc.nextInt();
				int d = sc.nextInt();
				node.setP(p);
				node.setD(d);
				if(d > max) max = d;
				l.add(node);
			}
           Collections.sort(l);
           System.out.println(Main.getProfix(l , max));
		}
	}
	class Node implements Comparable{

		private int p;
		private int d;
		public int getP() {
			return p;
		}
		public void setP(int p) {
			this.p = p;
		}
		public int getD() {
			return d;
		}
		public void setD(int d) {
			this.d = d;
		}
		public int compareTo(Object o) {
			Node node = (Node)o;
			if (this.p > node.p){
				return 1;
			}else if(this.p < node.p){
				return -1;
			}else{
				return 1;
			}
		}
		
	}
}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }