A40815. 采油
题目描述
采油
题目描述
LQ公司是世界著名的石油公司，为世界供应优质石油。
最近，LQ公司又在森林里发现了一大片区域的油田，可以在这个油田中开采n个油井。
LQ公司在这n个油井之间修建了n-1条道路，每条道路连接两个油井，路径中间不会路过任何油井，而且这些道路将所有油井连通。
建立油井的时候需要使用一台大型设备，运输起来非常麻烦，LQ公司准备在其中的一个油井位置建立一个空运站，先将设备空运到空运站，之后每次经过他们建立的道路来运输这个大型设备以建立不同的油井，当油井建立完毕后再从空运站将大型设备运走。
为了减少运输的麻烦，公司要求大型设备在道路上运输的总路程是最短的。
在建立油井和采油的过程中需要花费一些人力，第i个油井需要花费Bi个人，而一旦油井建成，就需要Si个人一直坚守在油井上进行维护。
当然，如果一个人参与了油井的建设，他可以直接留下来维护油井，或者参与下一个油井的建设，但是在维护油井的人不能再参加后续油井的建设了。
现在LQ公司想知道，大型设备运输的总路径长度最短是多少？在保证总路径长度最短的情况下，LQ公司至少需要花费多少人力才能完成所有油井的建立与维护。
输入格式
输入的第一行包含一个整数n，表示油井的数量。油井由1到n依次标号。
第二行包含n个整数，依次表示B1, B2, …, Bn，相邻的整数之间用一个空格分隔。
第三行包含n个整数，依次表示S1, S2, …, Sn，相邻的整数之间用一个空格分隔。
接下来n-1行描述油井之间的道路，其中的第i行包含两个整数a，b，用一个空格分隔，表示一条道路的起点为i+1、终点为a，长度为b，道路是双向的，设备可以从任意一端运送到另一端，每条道路都可以经过任意多次。数据保证任意两个油井之间都可以通过道路连接。
输出格式
输出包含两个整数，用一个空格分隔，表示最优情况下大型设备需要运输的总路程，以及在总路程最短的情况下最少需要花费的人力数量。
样例输入
2
10 20
15 15
1 8
样例输出
16 30
样例说明
有两种方案达到最优。
方案一：在油井2建立空运站，先建立油井2，再将大型设备运输到油井1建立油井1，最后将大型设备运回油井2。
方案二：在油井1建立空运站，先将大型设备运输到油井2建立油井2，再将大型设备运送到油井1建立油井1。
样例输入
63 10 20 7 15 92 6 10 4 8 71 91 22 53 43 7
样例输出
54 38
数据规模和约定
对于20%的数据：n不超过10；
另外20%的数据：每个油井最多和两个油井之间有道路直接连接；
另外10%的数据：有n-1个油井只有一条道路与其他油井连接；
对于100%的数据：n不超过100000，B、S、c均为不超过10000的正整数。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
参考答案
import java.util.Scanner;
public class Main {
public static int n = 0;//表示油井的数量。油井由1到n依次标号。
public static int [] B;//第i个油井需要花费Bi个人
public static int [] S;//而一旦油井建成，就需要Si个人一直坚守在油井上进行维护。
public static int width = 0;//总路程
public static int count = 0;//人数
public static int ind = 0;//设备位置
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
B = new int [n+1];
S = new int [n+1];
for(int i=1;i<=n;i++){
B[i] = in.nextInt();
}
int con = 0;
for(int i=1;i<=n;i++){
S[i] = in.nextInt();
con+=S[i];
}
for(int i=2;i<=n;i++){
int a1 = in.nextInt();//终点
int b1 = in.nextInt();//长度
width+=b1;
}
show(con);//计算人数
System.out.println(width*2+" "+count);
}
/**
* B[i] 是第i个油井有多少人
* @param con 一共需要留守的人数
* 可以转化为求这些数的和大于con的最小值
*/
private static void show(int con) {
sort();
pd(con);
}
//算出大于con的最小值
private static void pd(int con) {
int coun = 0;
//从后往前累加
int d = 0;
for(int i=n;coun<con;i--){
coun+=B[i];
d = i;
}
if(coun>con){
coun-=B[d];
for(int i=1;coun<con;i++){
coun+=B[i];
}
}
count = coun;
}
//冒泡排序
private static void sort() {
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
if(B[i]>B[j]){
int temp = B[i];
B[i] = B[j];
B[j] = temp;
}
}
}
}
}