[已解决]C++题目求助

Lynn_oyl

请问有大佬知道这道题怎么做吗？

说明
输入 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

最佳答案

月排行榜 / 总排行榜

陶远航

2023-10-2 13:28:38

Lynn_oyl 发表于 2023-10-2 13:26
可是我现在还没有学到vector

你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：

#include <iostream>

using namespace std;

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

    int points[n][2];
    int power[n + 1] = {0};

    for (int i = 0; i < n; i++) {
        cin >> points[i][0] >> points[i][1];
    }

    int maxPower = 0;
    int maxPowerIndex = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (points[j][0] < points[i][0] && points[j][1] < points[i][1]) {
                power[i + 1]++;
            }
        }

        if (power[i + 1] > maxPower) {
            maxPower = power[i + 1];
            maxPowerIndex = i + 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << power[i] << endl;
    }

    cout << maxPowerIndex << endl;

    return 0;
}

这段代码用数组代替了vector来存储点的坐标和战斗力，其余的逻辑保持不变。希望对你有所帮助！如果你对这段代码有任何疑问，请随时追问。

跳转到最佳答案楼层

陶远航

Lynn_oyl 发表于 2023-10-2 13:26
可是我现在还没有学到vector

你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：

#include <iostream>

using namespace std;

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

    int points[n][2];
    int power[n + 1] = {0};

    for (int i = 0; i < n; i++) {
        cin >> points[i][0] >> points[i][1];
    }

    int maxPower = 0;
    int maxPowerIndex = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (points[j][0] < points[i][0] && points[j][1] < points[i][1]) {
                power[i + 1]++;
            }
        }

        if (power[i + 1] > maxPower) {
            maxPower = power[i + 1];
            maxPowerIndex = i + 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << power[i] << endl;
    }

    cout << maxPowerIndex << endl;

    return 0;
}

这段代码用数组代替了vector来存储点的坐标和战斗力，其余的逻辑保持不变。希望对你有所帮助！如果你对这段代码有任何疑问，请随时追问。

isdkz

这道题可以使用二维树状数组进行求解。

思路：

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[j].first < points[ i].first && points[j].second < points[ i].second) {
                power[i + 1]++;
            }
        }

        if (power[i + 1] > maxPower) {
            maxPower = power[i + 1];
            maxPowerIndex = i + 1;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << power[ i] << endl;
    }

    cout << maxPowerIndex << endl;

    return 0;
}

希望能帮助到你解决这道题。如果有任何疑问，请随时追问。
如果问题已经解决，请设置最佳答案

Lynn_oyl

陶远航 发表于 2023-10-2 13:24
这道题可以使用暴力求解的方法来解决。对于每个点，遍历所有位于它左下方的点，统计它可以控制的点的数量， ...

可是我现在还没有学到vector

Lynn_oyl

陶远航 发表于 2023-10-2 13:28
你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：

谢谢大佬！

Lynn_oyl

陶远航 发表于 2023-10-2 13:28
你可以使用数组来代替vector来存储点的坐标和战斗力。下面是相应的代码，它使用了数组来完成：

这是我自己写的代码：

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >>n;
    int point[n][2],power[n]={};
    for(int i=0;i<n;i++) cin>>point[i][0]>>point[i][1];
    int max=0,id=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(point[i][0]>point[j][0]&&point[i][1]>point[j][1]) power[i]++;
        }
        if(power[i]>=max){
            max=power[i];
            id=i+1;
        }
    }
    for(int i=0;i<n;i++) cout<<power[i]<<endl;
    cout<<id;
    return 0;
}