题目地址：http://acm.hdu.edu.cn/showproblem.php?pid=4882
题解：参考题后Discuss javaherongwei 的讲解
考察序列中相邻的两题i, j(i在前)。交换它们后，解出它们之前的题目所带来的时间对答案的贡献是不变的，它们对它们后面的题目的贡献也是不变的，其他题目之间对答案的贡献自然也是不变的。唯一的变化就是，原来的EiKj一项变成了EjKi一项。那么，为了使答案变优，需要满足的条件是EjKi≤EiKj。也即Ei/Ki≥Ej/Kj。那么，最优解序列Ai一定满足，EAi/KAi是递增的。排序一遍即可。
JAVA实现的AC代码 注意使用long类型
1 import java.io.BufferedInputStream; 2 import java.util.*; 3 4 class Problem { 5 long e, k; 6 double x; 7 8 public Problem() { 9 10 } 11 } 12 13 class MyComparator implements Comparator { 14 15 @Override 16 public final int compare(Object o1, Object o2) { 17 if (((Problem) o1).x > ((Problem) o2).x) 18 return 1; 19 else if (((Problem) o1).x == ((Problem) o2).x) 20 return 0; 21 else 22 return -1; 23 } 24 25 } 26 27 public class Main { 28 29 public static void main(String[] args) { 30 31 Scanner in = new Scanner(new BufferedInputStream(System.in)); 32 while (in.hasNext()) { 33 int T = in.nextInt(); 34 Problem p[] = new Problem[T]; 35 36 for (int i = 0; i < T; i++) { 37 p[i] = new Problem(); 38 p[i].e = in.nextLong(); 39 } 40 41 for (int i = 0; i < T; i++) { 42 p[i].k = in.nextLong(); 43 p[i].x = 1.0 * p[i].e / (1.0 * p[i].k); 44 } 45 46 Arrays.sort(p, new MyComparator()); 47 long sum = 0; 48 long ans = 0; 49 for (int i = 0; i < T; i++) { 50 sum += p[i].e; 51 ans += sum * p[i].k; 52 } 53 54 55 System.out.println(ans); 56 } 57 } 58 59 }