求调站外水题

题目描述

在一条公路两旁，散布着

n

个小区，小区里有若干个学龄儿童。但这条路上还没有学校，现准备在这条路上的任选一点（可以和小区重合，也可以不重合）建学校，使得所有学生走的路程最短。

输入格式第1行：一个整数

n

（

1 <= n <= 100000

），表示公路两旁小区的数量。接下来的

n

行，每行

2

个整数

a_i

和

b_i

，分别表示小区的位置（将公路看成起点为0的一条数轴）和小区里学龄儿童的人数。

输出格式一个数，表示所有学生走的最小的路程之和。

样例输入

5
1 2
10 4
20 3
30 5
40 2

样例输出

168

提示

学校选建在

20

这个位置，所有学生走的路程和为：

19×2＋10×4＋10×5＋20×2＝168

，这个路程和是最短的。

CPP

#include <bits/stdc++.h>
#define int long long
#define JS ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;

struct Node {
	int p, q, num;
} a[100001];

bool cmp(Node x, Node y) {
	return x.num < y.num;
}
int n, tmp, t, sum;

signed main() {
	JS;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].p >> a[i].q;
		a[i].num = a[i].p * a[i].q;
	}
	sort(a + 1, a + 1 + n, cmp);
	if (n % 2 == 0) {
		t = a[n / 2].p;
	}
	if (n % 2 == 1) {
		t = a[n / 2 + 1].p;
	}
	for (int i = 1; i <= n; i++) {
		\\cout << abs(t - a[i].p) << " * " << a[i].q << endl << sum << endl << endl;
		sum += abs(t - a[i].p) * a[i].q;
	}
	cout << sum;
	return 0;
}

25pts，我连膜你赛T2都切不掉了（？？？）

讨论操作

回复

相关推荐

求调站外水题