本文共 2329 字，大约阅读时间需要 7 分钟。
Arthur最近搬到了新的别墅，别墅特别大，原先的桌子显得比较小，所以他决定换一张新的桌子。他买了一张特别大的桌子，桌子是由很多条桌腿进行支撑的，可是回到家之后他发现桌子不稳，原来是桌子腿长度不太相同。他想要自己把桌子修理好，所以他决定移除掉一些桌腿来让桌子变得平稳。桌子腿总共有n条腿，第i条腿长度为li，Arthur移除第i桌腿要花费代价为di。假设k条腿桌子平稳的条件:超过一半桌腿能够达到桌腿长度的最大值。例如：一条腿的桌子是平稳的，两条腿的桌子腿一样长时是平稳的。请你帮Arthur计算一下是桌子变平稳的最小总代价。
输入描述:
输入: 第一行数据是一个整数：n (1≤n≤105)，n表示桌腿总数。 第二行数据是n个整数：l1, l2, ..., ln (1≤li≤105)，表示每条桌腿的长度。 第三行数据是n个整数：d1, d2, ..., dn (1≤di≤200)，表示移除每条桌腿的代价。
输出描述:
输出: 输出让桌子变平稳的最小总代价
输入例子:
样例输入62 2 1 1 3 34 3 5 5 2 1
输出例子:
8
思路就是：把所有长度的桌腿都遍历一遍，把比保留长度桌腿长的全部剪掉，比保留桌腿短的按照代价，剪掉一部分，以保证要保留的腿数占总数的一般以上。
import java.util.ArrayList;import java.util.Collections;import java.util.Scanner;public class ZhuoTui { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //最小代价 int minCount = 0; ArrayList li = new ArrayList (); ArrayList di = new ArrayList (); //统计桌腿长度一样的桌腿数 int[] a = new int[106]; for (int i = 0; i < 106; i++) { a[i] = 0; } int n = sc.nextInt(); //桌腿长度 for (int i = 0; i < n; i++) { int num = sc.nextInt(); li.add(num); a[num] += 1; } //对应的桌腿代价 for (int i = 0; i < n; i++) { int num = sc.nextInt(); di.add(num); minCount += num; } //每次保留一个长度的桌腿，从最长的开始，使它站总长度的一半以上 for (int i = 105; i > 0; i--) { //把其他桌腿减掉，以满足条件的，最小代价 int cost = 0; //需要剪掉的桌腿集合，比要保留的桌腿长的，肯定要减去，比要保留桌腿短的，按照代价排序后，减去一部分。 ArrayList cut = new ArrayList (); if (a[i] > 0) { //cutNum要减去的桌腿数， int cutNum = li.size() - a[i]; for (int j = i + 1; j < 106; j++) { cutNum -= a[j]; } //其实这二步合起来就是cutNum=cutNum+1-2a[i];cutNum是去掉比要保留长度长的桌腿之后的总数 //假设要保留的桌腿长度的桌腿数为a[i]，那么要是桌子保持稳定，最后的桌腿总数肯定是2a[i]-1 cutNum -= (a[i] - 1); for (int k = 0; k < li.size(); k++) { //如果要保留长度小于要保留长度，则保存到待剪去的集合里 if (li.get(k) < i) { cut.add(di.get(k)); } //如果长度比要保留的长度大，直接剪去即可 if (li.get(k) > i) { cost += di.get(k); } } //对带剪去的集合按代价进行排序，剪掉代价最小的cutNum个 if (cut.size() > 0) { if (cutNum <= 0) { cutNum = 1; } Collections.sort(cut); for (int k = 0; k < cutNum; k++) { cost += cut.get(k); } //如果此次的代价小于全局的最小代价，则这次代价就是当前的最小代价 if (cost < minCount) { minCount = cost; } } } } System.out.println(minCount); }} 转载地址：http://xebrb.baihongyu.com/