C++: [CSP-J2022 山东补测] 宴会 (banquet) - 最优宴会地点求解 - 常规

C++: [CSP-J2022 山东补测] 宴会 (banquet) - 最优宴会地点求解

今人不见古时月，今月曾经照古人。梦回长安，大唐风华，十里长安花，一日看尽。

唐长安城是当时世界上规模最大、建筑最宏伟、规划布局最为规范化的一座都城。其营建制度规划布局的特点是规模空前、创设皇城、三城层环、六坡利用、布局对称、街衢宽阔、坊里齐整、形制划一、渠水纵横、绿荫蔽城、郊环祀坛。而所谓的十里长安街，位于长安城的中轴线上，即唐长安城的朱雀大街，又称承天门大街。唐朝官员们住在各个'坊'里，上朝下朝都需要通过朱雀大街。

为了保持各大家族的联系和友谊，各官员往往会每月办一次宴会。为了方便描述，我们把朱雀大街看成一个数轴，各官员所居住的'坊'缩略为数轴上的一个坐标点。大家决定选一处地点（该地点是数轴上的某一个点，不一定坐标点）办宴会。由于唐朝宵禁严格，大家又都希望交流时间尽可能长，因此想要使宴会开始时间尽可能早。又因为大唐注重礼仪，因此，参加宴会的官员会花一定时间盛装打扮过后才前往宴会地点（不一定是坐标点）。

题目描述

更具体地，一条纵向的街道上（相当于一维坐标）有 n 个人居住，其中第 i 个人居住在 xi（非负整数）位置（坐标点）上。每月他们会选择在 x0（数轴上的某一个点，不一定坐标点）处举办宴会。

已知第 i 个人从 xi 出发前往宴会地点 x0 处需要花费 |xi-x0| 的时间，另外，他还需要花费 ti 的时间进行打扮，换言之，他共需要花费 |xi-x0|+ti 的时间到达宴会举办处。

假设初始时刻为 0。这 n 个人开始打扮和出发前往宴会处，他们想要使得宴会的开始时间尽可能早，于是向你求助，请你帮助他们确定好最优的宴会举办地点 x0。

注：|xi-x0| 表示 xi 与 x0 之差的绝对值，且题目中 n 个人的居住地点坐标均为整数。

输入格式

第一行一个正整数 T，表示测试数据的组数。

接下来对于每组测试数据（注意：每组测试数据有 3 行数据，以下共 3 × T 行数据）：

第一行一个正整数 n，表示总官员人数。

第二行共 n 个非负整数 x1,x2,...,xn 分别表示这 n 个人在数轴上的坐标。

第三行共 n 个非负整数 t1,t2,...,tn 分别表示这 n 个人出发前的打扮时间。

输出格式

共输出 T 行数据，对于每组测试数据，输出一行一个实数（如果是整数按整数输出，如果有小数，保留 1 位小数输出），表示使宴会开始时间最早的最优举办地点坐标 x0。（很显然，x0 都是唯一的）

样例 #1

样例输入 #1

7
1
0
3
2
3 1
0 0
2
1 4
0 0
3
1 2 3
0 0 0
3
1 2 3
4 1 2
3
3 3 3
5 3 3
6
5 4 7 2 10 4
3 2 5 1 4 6

样例输出 #1

提示

样例解释

初始时刻为 0。

对于第一组测试数据只有 1 个人，坐标为 0，打扮时间为 3，很显然 x0 就定在坐标 0 处，使得宴会开始时间为 3 且最早。

对于第二组测试数据有 2 个人，坐标分别为 3、1，打扮时间均为 0，很显然 x0 定在坐标 2 处，使得宴会开始时间为 1 且最早。

对于第三组测试数据有 2 个人，坐标分别为 1、4，打扮时间均为 0，很显然 x0 定在坐标 2.5 处，使得宴会开始时间为 1.5 且最早。

题解思路

由于每个人到达宴会地点的时间取决于他到宴会地点的距离和他的打扮时间，我们可以枚举每个人的坐标作为宴会地点，计算每个人到达宴会地点的时间，最后找到使总时间最小的宴会地点。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        cin >> n;

        vector<int> x(n);
        vector<int> t(n);
        for (int i = 0; i < n; i++) {
            cin >> x[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> t[i];
        }

        sort(x.begin(), x.end());

        int minTime = INT_MAX;
        double bestX = 0;

        for (int i = 0; i < n; i++) {
            double curX = x[i];
            int totalTime = 0;

            for (int j = 0; j < n; j++) {
                totalTime += abs(x[j] - curX) + t[j];
            }

            if (totalTime < minTime) {
                minTime = totalTime;
                bestX = curX;
            }
        }

        cout << bestX << endl;
    }

    return 0;
}

代码说明

首先，我们读取输入数据，并将每个人的坐标和打扮时间存储在 x 和 t 数组中。
然后，我们对 x 数组进行排序，这样可以方便我们枚举每个人的坐标作为宴会地点。
接下来，我们枚举每个人的坐标作为宴会地点，计算每个人到达宴会地点的时间，并记录总时间最小的宴会地点。
最后，我们输出使宴会开始时间最早的最优举办地点坐标。

总结

本题的解题思路比较简单，只需要枚举每个人的坐标作为宴会地点，计算每个人到达宴会地点的时间，并记录总时间最小的宴会地点即可。代码实现也很简单，只需要使用循环和绝对值函数即可。

C++: [CSP-J2022 山东补测] 宴会 (banquet) - 最优宴会地点求解