做不锈钢的网站有哪些,知名建站公司,对于协会的新年祝贺语网站模板,软件开发自学网题目 思路和解题方法 这段代码的目标是计算给定点集的最小总移动成本#xff0c;使得所有点都在同一直线上。它通过计算每个点左边和右边的移动成本#xff0c;然后在所有可能的分割点中选择最小成本。具体步骤如下#xff1a; 读取输入的点集#xff0c;每个点表示为 (y, …
题目 思路和解题方法 这段代码的目标是计算给定点集的最小总移动成本使得所有点都在同一直线上。它通过计算每个点左边和右边的移动成本然后在所有可能的分割点中选择最小成本。具体步骤如下 读取输入的点集每个点表示为 (y, x)其中 y 是点的权重x 是点的位置。对点集按照 x 坐标进行排序。计算每个点左边和右边的移动成本。遍历每个可能的分割点计算总成本并记录最小成本。输出最小成本。 复杂度 时间复杂度:O(nlogn) 时间复杂度: 排序所需的时间复杂度为 O(nlogn)计算移动成本的过程需要线性时间因此总体时间复杂度为 O(nlogn)。 空间复杂度:O(n) 空间复杂度: 程序的空间复杂度主要取决于数组 p[]pre[]nex[] 和其他常量因此为 O(n)。 c 代码
#include bits/stdc.h
using namespace std;
const int N1e59;
#define x first
#define y second
typedef long long ll;
pairint,intp[N];
ll pre[N],nex[N];
int main() {int n;cinn;// 读入点集每个点的坐标为 (y, x)for(int i1;in;i)cinp[i].yp[i].x;// 按照 x 坐标对点集进行排序sort(p1,p1n);ll s0;// 计算每个点左边的移动成本for(int i1;in;i){pre[i]pre[i-1];pre[i]s*(p[i].x-p[i-1].x);sp[i].y;}s0;// 计算每个点右边的移动成本for(int in;i1;i--){nex[i]nex[i1];nex[i]s*(p[i1].x-p[i].x);sp[i].y;}ll ans1e18;// 遍历每个可能的分割点计算总成本并记录最小成本for(int i1;in;i){ansmin(ans,pre[i]nex[i]);}// 输出最小成本coutansendl;return 0;
}Java 版本仅供参考
import java.util.*;public class Main {static final int N 100009;public static void main(String[] args) {Scanner scanner new Scanner(System.in);int n scanner.nextInt();Pair[] p new Pair[N];long[] pre new long[N];long[] nex new long[N];for (int i 1; i n; i)p[i] new Pair(scanner.nextInt(), scanner.nextInt());Arrays.sort(p, 1, n 1);long s 0;for (int i 1; i n; i) {pre[i] pre[i - 1];pre[i] s * (p[i].x - p[i - 1].x);s p[i].y;}s 0;for (int i n; i 1; i--) {nex[i] nex[i 1];nex[i] s * (p[i 1].x - p[i].x);s p[i].y;}long ans Long.MAX_VALUE;for (int i 1; i n; i) {ans Math.min(ans, pre[i] nex[i]);}System.out.println(ans);}static class Pair implements ComparablePair {int y, x;Pair(int y, int x) {this.y y;this.x x;}public int compareTo(Pair other) {return Integer.compare(this.x, other.x);}}
}Python 版本仅供参考
n int(input())
p [(0, 0)] * (n 1)
pre [0] * (n 1)
nex [0] * (n 1)for i in range(1, n 1):p[i] tuple(map(int, input().split()))p.sort(keylambda x: x[1])s 0
for i in range(1, n 1):pre[i] pre[i - 1]pre[i] s * (p[i][1] - p[i - 1][1])s p[i][0]s 0
for i in range(n, 0, -1):nex[i] nex[i 1]nex[i] s * (p[i 1][1] - p[i][1])s p[i][0]ans float(inf)
for i in range(1, n 1):ans min(ans, pre[i] nex[i])print(ans)觉得有用的话可以点点赞支持一下。
如果愿意的话关注一下。会对你有更多的帮助。 每天都会不定时更新哦 人 。
