OR96. 合并果子
描述
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了N堆。果园是一个二维平面，第i堆果子的位置为(Xi,Yi)，重量为Wi。
多多决定把所有的果子合成一堆。每一次合并，多多可以消耗Wi (|Xi - Xj |+|Yi - Yj |)的体力把第i堆果子合并到第j堆。可以看出，所有的果子经过N-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
请你求出将所有果子合并成一堆消耗的总体力最少是多少。
输入描述
第一行一个正整数N，接下来N行每行三个正整数 Xi Yi Wi输出描述
一个数，最少消耗的总体力示例1
输入:
4 2 1 1 1 2 3 3 1 2 2 4 2
输出:
14
说明:
数据约定： 20% N≤10 60% N≤1000 100% N≤100000,Xi,Yi,Wi≤100000C++ 解法, 执行用时: 18ms, 内存消耗: 1688KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
struct node{
long long x, y;
};
node a[100000];
long long X[100001], Y[100001];
long long xadd[100001], xradd[100001], yadd[100001], yradd[100001];
int main(){
long long n, w, t;
long long xmin, xmax, ymin, ymax;
scanf("%lld", &n);
xmin = ymin = 100000;
xmax = ymax = 0;
for (long long i=0; i<n; ++i){
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &w);
X[a[i].x] += w;
Y[a[i].y] += w;
xmin = min(xmin,a[i].x);
xmax = max(xmax,a[i].x);
ymin = min(ymin,a[i].y);
ymax = max(ymax,a[i].y);
}
t = X[xmin];
for (long long i=xmin+1; i<=xmax; ++i){
xadd[i] = xadd[i-1] + t;
t += X[i];
}
t = X[xmax];
for (long long i=xmax-1; i>=xmin; --i){
xradd[i] = xradd[i+1] + t;
t += X[i];
}
t = Y[ymin];
for (long long i=ymin+1; i<=ymax; ++i){
yadd[i] = yadd[i-1] + t;
t += Y[i];
}
t = Y[ymax];
for (long long i=ymax-1; i>=ymin; --i){
yradd[i] = yradd[i+1] + t;
t += Y[i];
}
long long ans = 0;
for (long long i=0; i<n; ++i){
long long px = a[i].x;
long long py = a[i].y;
if (i==0)
ans = xadd[px]+xradd[px]+yadd[py]+yradd[py];
else
ans = min(ans,xadd[px]+xradd[px]+yadd[py]+yradd[py]);
}
cout << ans;
}
C++ 解法, 执行用时: 19ms, 内存消耗: 1568KB, 提交时间: 2020-10-31
#include <bits/stdc++.h>
using namespace std;
struct node{
long long x, y;
};
node a[100000];
long long X[100001], Y[100001];
long long xadd[100001], xradd[100001], yadd[100001], yradd[100001];
int main(){
long long n, w, t;
long long xmin, xmax, ymin, ymax;
scanf("%lld", &n);
xmin = ymin = 100000;
xmax = ymax = 0;
for (long long i=0; i<n; ++i){
scanf("%lld%lld%lld", &a[i].x, &a[i].y, &w);
X[a[i].x] += w;
Y[a[i].y] += w;
xmin = min(xmin,a[i].x);
xmax = max(xmax,a[i].x);
ymin = min(ymin,a[i].y);
ymax = max(ymax,a[i].y);
}
t = X[xmin];
for (long long i=xmin+1; i<=xmax; ++i){
xadd[i] = xadd[i-1] + t;
t += X[i];
}
t = X[xmax];
for (long long i=xmax-1; i>=xmin; --i){
xradd[i] = xradd[i+1] + t;
t += X[i];
}
t = Y[ymin];
for (long long i=ymin+1; i<=ymax; ++i){
yadd[i] = yadd[i-1] + t;
t += Y[i];
}
t = Y[ymax];
for (long long i=ymax-1; i>=ymin; --i){
yradd[i] = yradd[i+1] + t;
t += Y[i];
}
long long ans = 0;
for (long long i=0; i<n; ++i){
long long px = a[i].x;
long long py = a[i].y;
if (i==0)
ans = xadd[px]+xradd[px]+yadd[py]+yradd[py];
else
ans = min(ans,xadd[px]+xradd[px]+yadd[py]+yradd[py]);
}
cout << ans;
}