思路：x轴和y轴的情况是独立的，可以分开考虑，那么只要枚举位置，能维护最小值即可，这只要把公式拆开，预处理出两个前缀和即可，一个是w的前缀和，，一个是w * x的前缀和
代码：
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;const int N = 50005;typedef long long ll;int t, n, m, q;int x[N], y[N];ll sum[N][2], w[N];ll cal(int v, int n) {ll ans1 = sum[v][1] * v – sum[v][0];ll ans2 = (sum[n][0] – sum[v][0]) – (sum[n][1] – sum[v][1]) * v;return ans1 + ans2;}int gao(int *x, int n) {memset(sum, 0, sizeof(sum));for (int i = 0; i < q; i++) {sum[x[i]][0] += w[i] * x[i];sum[x[i]][1] += w[i];}for (int i = 1; i <= n; i++) {for (int j = 0; j < 2; j++)sum[i][j] += sum[i – 1][j];}int ans = 1;for (int i = 1; i <= n; i++) {if (cal(i, n) < cal(ans, n))ans = i;}return ans;}int main() {int cas = 0;scanf("%d", &t);while (t–) {scanf("%d%d%d", &n, &m, &q);for (int i = 0; i < q; i++)scanf("%d%d%lld", &x[i], &y[i], &w[i]);printf("Case %d: %d %d\n", ++cas, gao(x, n), gao(y, m));}return 0;}
天下无难事，只怕有心人。
