[已解决]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

1. 6                                                                0
   
2. 4 2                                                                1
   
3. 6 6                                                                0
   
4. 4 8                                                                1
   
5. 15 6                                                                3
   
6. 11 9                                                                3
   
7. 8 14                                                                6
   

复制代码

最佳答案

月排行榜 / 总排行榜

陶远航

2023-10-2 13:28:38

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

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

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.     int n;
   
7.     cin >> n;
   
8. 
   
9.     int points[n][2];
   
10.     int power[n + 1] = {0};
    
11. 
    
12.     for (int i = 0; i < n; i++) {
    
13.         cin >> points[i][0] >> points[i][1];
    
14.     }
    
15. 
    
16.     int maxPower = 0;
    
17.     int maxPowerIndex = 1;
    
18. 
    
19.     for (int i = 0; i < n; i++) {
    
20.         for (int j = 0; j < i; j++) {
    
21.             if (points[j][0] < points[i][0] && points[j][1] < points[i][1]) {
    
22.                 power[i + 1]++;
    
23.             }
    
24.         }
    
25. 
    
26.         if (power[i + 1] > maxPower) {
    
27.             maxPower = power[i + 1];
    
28.             maxPowerIndex = i + 1;
    
29.         }
    
30.     }
    
31. 
    
32.     for (int i = 1; i <= n; i++) {
    
33.         cout << power[i] << endl;
    
34.     }
    
35. 
    
36.     cout << maxPowerIndex << endl;
    
37. 
    
38.     return 0;
    
39. }

复制代码

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

跳转到最佳答案楼层

陶远航

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

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

1. #include <iostream>
   
2. 
   
3. using namespace std;
   
4. 
   
5. int main() {
   
6.     int n;
   
7.     cin >> n;
   
8. 
   
9.     int points[n][2];
   
10.     int power[n + 1] = {0};
    
11. 
    
12.     for (int i = 0; i < n; i++) {
    
13.         cin >> points[i][0] >> points[i][1];
    
14.     }
    
15. 
    
16.     int maxPower = 0;
    
17.     int maxPowerIndex = 1;
    
18. 
    
19.     for (int i = 0; i < n; i++) {
    
20.         for (int j = 0; j < i; j++) {
    
21.             if (points[j][0] < points[i][0] && points[j][1] < points[i][1]) {
    
22.                 power[i + 1]++;
    
23.             }
    
24.         }
    
25. 
    
26.         if (power[i + 1] > maxPower) {
    
27.             maxPower = power[i + 1];
    
28.             maxPowerIndex = i + 1;
    
29.         }
    
30.     }
    
31. 
    
32.     for (int i = 1; i <= n; i++) {
    
33.         cout << power[i] << endl;
    
34.     }
    
35. 
    
36.     cout << maxPowerIndex << endl;
    
37. 
    
38.     return 0;
    
39. }

复制代码

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

isdkz

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

思路：

1. 首先将输入的点按照横坐标从小到大排序，如果横坐标相同则按照纵坐标从小到大排序。

2. 从左下向右上扫描每个点，对于每个点，先查询比它横坐标小的点中纵坐标小于它的点的个数，然后将该点的纵坐标插入到树状数组中。

3. 查询比当前点横坐标小的点中纵坐标小于它的点的个数，即为该点的战斗力。

4. 维护一个变量，记录战斗力最大的点的编号。

5. 最后输出每个点的战斗力和战斗力最大的点的编号。

代码实现：

陶远航

这道题可以使用暴力求解的方法来解决。对于每个点，遍历所有位于它左下方的点，统计它可以控制的点的数量，即战斗力。

具体的实现步骤如下：

1. 读取输入的点的数量 n。

2. 创建一个大小为 n 的数组 power，用于存储每个点的战斗力。

3. 使用一个双重循环，外层循环遍历每个点，内层循环遍历位于该点左下方的点。

4. 对于每个点，统计位于它左下方的点的数量，并在 power 数组中更新对应点的战斗力。

5. 在遍历过程中，记录战斗力最高的点的编号和战斗力。

6. 输出每个点的战斗力，最后输出战斗力最高的点的编号。

根据上述思路，可以编写以下的代码实现：

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. using namespace std;
   
5. 
   
6. int main() {
   
7.     int n;
   
8.     cin >> n;
   
9. 
   
10.     vector<pair<int, int>> points(n);
    
11.     vector<int> power(n + 1, 0);
    
12. 
    
13.     for (int i = 0; i < n; i++) {
    
14.         cin >> points[ i].first >> points[ i].second;
    
15.     }
    
16. 
    
17.     int maxPower = 0;
    
18.     int maxPowerIndex = 1;
    
19. 
    
20.     for (int i = 0; i < n; i++) {
    
21.         for (int j = 0; j < i; j++) {
    
22.             if (points[j].first < points[ i].first && points[j].second < points[ i].second) {
    
23.                 power[i + 1]++;
    
24.             }
    
25.         }
    
26. 
    
27.         if (power[i + 1] > maxPower) {
    
28.             maxPower = power[i + 1];
    
29.             maxPowerIndex = i + 1;
    
30.         }
    
31.     }
    
32. 
    
33.     for (int i = 1; i <= n; i++) {
    
34.         cout << power[ i] << endl;
    
35.     }
    
36. 
    
37.     cout << maxPowerIndex << endl;
    
38. 
    
39.     return 0;
    
40. }
    

复制代码

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

Lynn_oyl

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

可是我现在还没有学到vector

Lynn_oyl

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

谢谢大佬！

Lynn_oyl

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

这是我自己写的代码：

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. int main(){
   
4.     int n;
   
5.     cin >>n;
   
6.     int point[n][2],power[n]={};
   
7.     for(int i=0;i<n;i++) cin>>point[i][0]>>point[i][1];
   
8.     int max=0,id=1;
   
9.     for(int i=0;i<n;i++){
   
10.         for(int j=0;j<n;j++){
    
11.             if(point[i][0]>point[j][0]&&point[i][1]>point[j][1]) power[i]++;
    
12.         }
    
13.         if(power[i]>=max){
    
14.             max=power[i];
    
15.             id=i+1;
    
16.         }
    
17.     }
    
18.     for(int i=0;i<n;i++) cout<<power[i]<<endl;
    
19.     cout<<id;
    
20.     return 0;
    
21. }

复制代码