C++题目求助
请问有大佬知道这道题怎么做吗？说明
输入 n 个点在平面上的坐标(横纵坐标都是整数)，对于每个点可以控制所有位于它左 下方的点(即横坐标 x 和纵坐标 y 都比它小)，它可以控制的点的数目称为“战斗力”。依次 输出每个点的战斗力，最后输出战斗力最高的点的编号(如果若干个点的战斗力并列最高， 输出其中最大的编号)。
输入格式
输入第一行包含一个正整数 n（1≤n≤100），接下来的 n 行，每行描述一个点的坐标，第 i+1 行包含两个正整数 x 和 y（1≤x,y≤1000），表示编号为 i 的点的横坐标为 x，纵坐标为 y。
输出格式
输出共有 n+1 行，第 1 行到第 n 行，每行包含一个整数，第 i 行的整数表示编号为 i 的点的战斗力，第 n+1 行表示战斗力最高的点的编号。
样例
输入数据 1 输出数据 1
6 0
4 2 1
6 6 0
4 8 1
15 6 3
11 9 3
8 14 6
Lynn_oyl 发表于 2023-10-2 13:26
可是我现在还没有学到vector
你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int points;
int power = {0};
for (int i = 0; i < n; i++) {
cin >> points >> points;
}
int maxPower = 0;
int maxPowerIndex = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (points < points && points < points) {
power++;
}
}
if (power > maxPower) {
maxPower = power;
maxPowerIndex = i + 1;
}
}
for (int i = 1; i <= n; i++) {
cout << power << endl;
}
cout << maxPowerIndex << endl;
return 0;
}
这段代码用数组代替了vector来存储点的坐标和战斗力，其余的逻辑保持不变。希望对你有所帮助！如果你对这段代码有任何疑问，请随时追问。 这道题可以使用二维树状数组进行求解。
思路：
1. 首先将输入的点按照横坐标从小到大排序，如果横坐标相同则按照纵坐标从小到大排序。
2. 从左下向右上扫描每个点，对于每个点，先查询比它横坐标小的点中纵坐标小于它的点的个数，然后将该点的纵坐标插入到树状数组中。
3. 查询比当前点横坐标小的点中纵坐标小于它的点的个数，即为该点的战斗力。
4. 维护一个变量，记录战斗力最大的点的编号。
5. 最后输出每个点的战斗力和战斗力最大的点的编号。
代码实现： 这道题可以使用暴力求解的方法来解决。对于每个点，遍历所有位于它左下方的点，统计它可以控制的点的数量，即战斗力。
具体的实现步骤如下：
1. 读取输入的点的数量 n。
2. 创建一个大小为 n 的数组 power，用于存储每个点的战斗力。
3. 使用一个双重循环，外层循环遍历每个点，内层循环遍历位于该点左下方的点。
4. 对于每个点，统计位于它左下方的点的数量，并在 power 数组中更新对应点的战斗力。
5. 在遍历过程中，记录战斗力最高的点的编号和战斗力。
6. 输出每个点的战斗力，最后输出战斗力最高的点的编号。
根据上述思路，可以编写以下的代码实现：
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<int, int>> points(n);
vector<int> power(n + 1, 0);
for (int i = 0; i < n; i++) {
cin >> points[ i].first >> points[ i].second;
}
int maxPower = 0;
int maxPowerIndex = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (points.first < points[ i].first && points.second < points[ i].second) {
power++;
}
}
if (power > maxPower) {
maxPower = power;
maxPowerIndex = i + 1;
}
}
for (int i = 1; i <= n; i++) {
cout << power[ i] << endl;
}
cout << maxPowerIndex << endl;
return 0;
}
希望能帮助到你解决这道题。如果有任何疑问，请随时追问。
如果问题已经解决，请设置最佳答案 陶远航 发表于 2023-10-2 13:24
这道题可以使用暴力求解的方法来解决。对于每个点，遍历所有位于它左下方的点，统计它可以控制的点的数量， ...
可是我现在还没有学到vector 陶远航 发表于 2023-10-2 13:28
你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：
谢谢大佬！ 陶远航 发表于 2023-10-2 13:28
你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：
这是我自己写的代码：
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
cin >>n;
int point,power={};
for(int i=0;i<n;i++) cin>>point>>point;
int max=0,id=1;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(point>point&&point>point) power++;
}
if(power>=max){
max=power;
id=i+1;
}
}
for(int i=0;i<n;i++) cout<<power<<endl;
cout<<id;
return 0;
}
页:
[1]