思想
!!!注意,以后用Arrays.sort的时候记得用对象创建数组(例如,Integer[] a, Long[] a等等)!!!我们希望知道把所有石头放在哪一个位置的花费是最低的,所以我们正向一次前缀和,反向一次前缀和,求min(pre[i]+nex[i])
代码
import java.io.*;
import java.util.Arrays;
public class Main {
static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 100010;
static long[] pre = new long[N]; //pre[i]表示前i-1个石头移动到第i个位置的费用
static long[] nex = new long[N]; //nex[i]表示前i-1个石头移动到第i个位置的费用
static stone[] a = new stone[N]; //石头的总重量
static long[] s = new long[N]; //排序后石头重量的前缀和
public static void main(String[] args)throws IOException{
int n = nextInt();
for(int i=1; i<=n; i++) a[i] = new stone(nextInt(), nextInt());
//根据石头位置对石头排序
Arrays.sort(a, 1, n+1, (o1, o2)->(o1.p-o2.p));
a[0] = new stone(0, 0); //为了方便后面计算前缀和建立的空石头
a[n+1] = new stone(0, 0);
//计算石头重量的前缀和数组(1->n)
for(int i=1; i<=n; i++) s[i] = s[i-1]+a[i].w;
//计算pre数组
for(int i=1; i<=n; i++) pre[i] = pre[i-1]+s[i-1]*(a[i].p-a[i-1].p);
//计算nex数组
for(int i=n; i>=1; i--) nex[i] = nex[i+1]+(s[n]-s[i])*(a[i+1].p-a[i].p);
//开始枚举放到哪个石头的位置费用最小
long ans = Long.MAX_VALUE;
for(int i=1; i<=n; i++){
ans = Math.min(ans, pre[i]+nex[i]);
}
out.println(ans);
out.flush();
out.close();
}
public static int nextInt()throws IOException{
in.nextToken();
return (int)in.nval;
}
public static long nextLong()throws IOException{
in.nextToken();
return (long)in.nval;
}
}
class stone{
int w; //石头的重量
int p; //石头的位置
public stone(int w, int p){
this.w = w;
this.p = p;
}
}