2013
11-11

# 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){
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;