P9569 Khronostasis Katharsis 题解
dsy2022
·
·
个人记录
1.理解题目：
我们有 n 个气球，每个气球初始高度为 0 米，然后在不同的时间剪断栓绳后，会以固定的速度上升。我们需要在第 T 秒时找到最高的气球中编号最小的一个气球的编号。
先想到的办法，不就排个序吗，两分半搞定，然后写出以下代码:
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
pair<int, int> a[maxn];
int n, t, x, y;
int main(){
cin >> n >> t;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
a[i] = make_pair(x * (t - y), i);
}
sort(a + 1, a + n + 1);
cout<<a[n].second << endl;
return 0;
}
所以我们只好从新审视问题
#### 2.问题分析：
从问题的描述中，我们可以看到每个气球的高度变化是线性的：高度 $=$ 初始高度 $+$ 速度 $\times$ 时间。因此，在给定的时间 $T$ 内，我们可以计算每个气球在第 $T$ 秒时的高度，然后找到其中高度最大的气球。注意，如果有多个气球高度相同，我们需要选择编号最小的气球。
#### 3.解决办法：
创建一个结构体 $\operatorname{Balloon}$ 来存储气球的信息：速度 $v$、剪断栓绳的时间 $t$、在第 $T$ 秒时的高度 $\operatorname{height}$ 和气球的编号 $\operatorname{number}$。
定义一个比较函数 $\operatorname{compareBalloon}$，用于在排序时比较气球的高度。如果两个气球的高度相同，那么根据气球的编号升序排列；否则，根据高度降序排列。这样，我们在排序后，第一个气球就是最高的气球中编号最小的一个。
主函数开始读取输入数据：气球的个数 $n$ 和时间 $T$。然后，我们创建一个大小为 $n$ 的 $\operatorname{balloons}$ 向量，用于存储每个气球的信息。
在循环中，读取每个气球的速度 $v_{i}$ 和剪断栓绳的时间 $t$。然后，我们可以根据公式 高度 $=$ 初始高度 $+$ 速度 $\times$ 时间 计算每个气球在第 $T$ 秒时的高度，并将气球的编号设为 $i + 1$。
使用 $\operatorname{C}$++ 的 $\operatorname{sort}$ 函数对 $\operatorname{balloons}$ 向量进行排序，排序的依据是通过比较函数 $\operatorname{compareBalloon}$。排序后，第一个气球就是最高的气球中编号最小的一个。
输出排序后的 $\operatorname{balloons}$ 向量中的第一个气球的编号，即编号最小的最高气球的编号。
#### 4.$\operatorname{AC}$ 代码：
```
#include <bits/stdc++.h>
using namespace std;
struct Balloon {
int v; // 气球速度
int t; // 剪断栓绳时间
int height; // 在第 T 秒时的高度
int number; // 气球编号
};
// 比较函数，用于排序气球
bool compareBalloon(const Balloon &a, const Balloon &b) {
if (a.height == b.height) {
return a.number < b.number; // 高度相同，按编号升序排序
}
return a.height > b.height; // 按高度降序排序
}
int main(){
int n, T;
cin >> n >> T;
vector<Balloon> balloons(n);
// 读取每个气球的信息并计算高度
for (int i = 0; i < n; i++) {
cin >> balloons[i].v >> balloons[i].t;
balloons[i].height = balloons[i].v * (T - balloons[i].t);
balloons[i].number = i + 1; // 设置气球编号
}
// 使用比较函数对气球进行排序
sort(balloons.begin(), balloons.end(), compareBalloon);
// 输出最高气球中编号最小的一个气球的编号
cout << balloons[0].number << endl;
return 0;
}
```
最后祝大家 rp++ 加油，拜拜！