首页 > 专题系列 > Java解POJ > POJ 2291 Rotten Ropes [解题报告] Java
2013
11-11

POJ 2291 Rotten Ropes [解题报告] Java

Rotten Ropes

问题描述 :

Suppose we have n ropes of equal length and we want to use them to lift some heavy object. A tear-off weight t is associated to each rope, that is, if we try to lift an object, heavier than t with that rope, it will tear off. But we can fasten a number of ropes to the heavy object (in parallel), and lift it with all the fastened ropes. When using k ropes to lift a heavy object with weight w, we assume that each of the k ropes, regardless of its tear-off weight, is responsible for lifting a weight of w/k. However, if w/k > t for some rope with tear-off weight of t, that rope will tear off. For example, three ropes with tear-off weights of 1, 10, and 15, when all three are fastened to an object, can not lift an object with weight more than 3, unless the weaker one tears-off. But the second rope, may lift by itself, an object with weight at most 10. Given the tear-off weights of n ropes, your task is to find the weight of the heaviest object that can be lifted by fastening a subset of the given ropes without any of them tearing off.

输入:

The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains a single integer n (1 <= n <= 1000) which is the number of ropes. Following the first line, there is a single line containing n integers between 1 and 10000 which are the tear-off weights of the ropes, separated by blank characters.

输出:

Each line of the output should contain a single number, which is the largest weight that can be lifted in the corresponding test case without tearing off any rope chosen.

样例输入:

2
3
10 1 15
2
10 15

样例输出:

20
20

解题代码:

//* @author popop0p0popo
import java.util.*;
import java.io.*;

public class Main{
 public static void main(String[] args){
   Scanner scanner=new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int t=scanner.nextInt();
		int n,max;
		int[] r;
		for (int i=0;i< t ;i++ ){
			n=scanner.nextInt();
			r=new int[n];
			for (int j=0;j< n ;j++ ){
				r[j]=scanner.nextInt();
			}
			intSort(r,0,n-1);
			max=n*r[0];
			for (int j=1;j< n ;j++ ){
				if ((n-j)*r[j]>max){
					max=(n-j)*r[j];
				}
			}
			System.out.println(max);
		}
	}

	public static void intSort(int[] number,int left,int right){
        if (left< right){
            int s=number[(left+right)/2];
            int i=left-1;
            int j=right+1;
            while (true){
                while (number[++i]< s);
                while (number[--j]>s);
                if (i>=j) break;
                swap(number,i,j);
            }
            intSort(number,left,i-1);
            intSort(number,j+1,right);
        }
    }

	public static void swap(int[] number,int i,int j) {
        int t;
        t=number[i];
        number[i]=number[j];
        number[j]=t;
    }
}

  1. 一开始就规定不相邻节点颜色相同,可能得不到最优解。我想个类似的算法,也不确定是否总能得到最优解:先着一个点,随机挑一个相邻点,着第二色,继续随机选一个点,但必须至少有一个边和已着点相邻,着上不同色,当然尽量不增加新色,直到完成。我还找不到反例验证他的错误。。希望LZ也帮想想, 有想法欢迎来邮件。谢谢

  2. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  3. 在方法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的边不是都没了吗?