新浪微博 登陆  注册   设为首页 加入收藏

学PHP >> 设计模式与算法 >> HDU 1051 贪心算法

HDU 1051 贪心算法

查看次数12106 发表时间2012-08-01 00:04:47

http://acm.hdu.edu.cn/showproblem.php?pid=1051

题目大意:

给n根木棍的长度和重量。根据要求求出制作木棍的最短时间。建立第一个木棍需要1分钟,若是接着要制作的木棍重量和长度都比此木棍长就不需要建立的时间,若是没有,则再需要建立时间。求时间最小为多少。

解题思路:

对木棍的长度和重量进行排序,以长度为首要考虑。排序完后的不一定都是下一根木棍重量和长度都大于前一根的。于是,我们对排序后的数组进行多次扫描,将可以在一次建立时间内完成的进行标记,知道木棍全部标记(设置一个外部变量来计数已扫描的元素的数量)。

例子:

5

4 9  5 2 2 1  3 5  1 4

排序完后:

1 4  2 1 3 5 4 9 5 2

然后进行第一次扫描:使用mark[]数组进行标记,mark[]初始化为0,红色为第一次描过的。

Stiks: (1 4)  (2 1)  (3 5)  (4 9)  (5 2)

Mark:   1       0      1       1      0

这是的setuptime为建立第一根木棍所要的时间,即1,此时扫描计数为3

接着进行第二次扫描,蓝色为第二次扫描过的结果。

Stiks: (1 4)  (2 1)  (3 5)  (4 9)  (5 2)

Mark:   1       0       1       1       0

这是的setuptime为1,此时扫描计数为5

代码如下:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;
class Node implements Comparable<Node>{
	int length;
	int weight;
	public Node(int length,int weight) {
		this.length = length;
		this.weight = weight;
	}
	@Override
	public int compareTo(Node o) {
		if(this.length > o.length){
			return 1;
		}
		else if( this.length == o.length){
			if(this.weight > o.weight){
				return 1;
			}else{
				return -1;
			}
		}
		return -1;
	}
}
public class HDU1051 {
	List<Node> list = new ArrayList<Node>();
	boolean mark[];
	
	public void solve(){
		Scanner sc = new Scanner(System.in);
		int co = sc.nextInt();
		for(int i=0; i<co; i++){
			int an = 0;
			list.clear();
			int marknum = 0;
			int n = sc.nextInt();
			mark = new boolean[n];
			for(int j=0; j<n; j++){
				int l = sc.nextInt(),w = sc.nextInt();
				Node node = new Node(l,w);
				list.add(node);
			}
			Collections.sort(list);
			while(marknum != n ){
				Node temp = new Node(-1,-1);
				an ++;
				for(int j=0; j<list.size(); j++){
					if( !mark[j]){
						Node node = list.get(j);
						if(node.weight >= temp.weight){
							mark[j] = true;
							temp = node;
							marknum ++;
						}
					}
				}
			}
			System.out.println(an);
		}
	}
	public static void main(String[] args) {
		new HDU1051().solve();
	}
	
}





(转发请注明转自:学PHP)    


  相关推荐



1楼 Star说: 2016-12-22 10:26:01
. I only eventually got access to real medical care that saved my life because I had an uncle who was a high ranking military surgeon and my grnrt-gaaedfather was a popular lecturer at the medical institute.In countries where government runs health care you have to know people and be prepared to bribe to get the health care our congress is making available only to themselves.

  发表评论
昵称:
(不超过20个字符或10个汉字)
内容: