#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a[n],b[n]; for(int i=0;i<n;i++) cin>>a[i]>>b[i]; for(int i=0;i<n;i++) { for(int j=i+1;j<n;j++) { if(a[i]==a[j]) { b[i]+=b[j]; } } } int max=0; for(int i=0;i<n;i++) { if(max<b[i]) max=b[i]; } for(int i=0;i<n;i++) { if(max==b[i]) { cout<<a[i]<<" "<<b[i]<<endl; break; } } return 0; }时间优化
时间: 2024-01-19 07:03:10 浏览: 36
可以考虑使用哈希表来优化时间复杂度。具体做法是,用一个哈希表来记录每个 a 值对应的 b 值的和,遍历输入数组时,将每个 a 值对应的 b 值加入哈希表中。最后再遍历哈希表,找到 b 值最大的对应的 a 值即可。
代码示例:
```c++
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
unordered_map<int, int> mp; // 哈希表
for (int i = 0; i < n; i++) {
int a, b;
cin >> a >> b;
mp[a] += b; // 将每个 a 值对应的 b 值加入哈希表
}
int max_b = 0, max_a;
for (auto p : mp) { // 遍历哈希表,找到 b 值最大的对应的 a 值
if (p.second > max_b) {
max_b = p.second;
max_a = p.first;
}
}
cout << max_a << " " << max_b << endl;
return 0;
}
```
时间复杂度为 O(n),空间复杂度为 O(n)。
相关问题
#include <bits/stdc++.h> using namespace std;
这个头文件是C++11标准引入的,它包含了所有标准库中的头文件。使用这个头文件可以方便地在一个地方包含所有需要的头文件,而不需要一个一个地包含。这个头文件通常只在竞赛中使用,因为它不是标准C++头文件,不保证在所有编译器中都能正常工作。
以下是一个使用这个头文件的示例,实现输入4个整数a、b、c、d,将它们倒序输出:
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d;
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```
`#include+<bits/stdc++.h>
`#include <bits/stdc++.h>`是一个非标准的头文件,它包含了STL中所有的头文件,因此可以方便地使用STL中的各种数据结构和算法。但是需要注意的是,这个头文件并不是所有编译器都支持,比如在一些嵌入式系统中就不支持。如果你想在使用这个头文件的时候避免出现问题,可以使用以下两种方法:
1.手动添加需要的头文件,比如如果你只需要使用vector和algorithm,可以这样写:
```cpp
#include <vector>
#include <algorithm>
```
2.使用预编译头文件,将需要的头文件都包含在一个文件中,然后在需要使用的文件中包含这个预编译头文件。这样可以加快编译速度,但是需要注意的是,预编译头文件可能会占用较多的内存。
下面是一个使用`#include <bits/stdc++.h>`的示例,实现:依次输入4个整数a、b、c、d,将它们倒序输出,即依次输出d、c、b、a这4个数。
```cpp
#include <bits/stdc++.h>
using namespace std;
int a, b, c, d;
int main() {
cin >> a >> b >> c >> d;
cout << d << ' ' << c << ' ' << b << ' ' << a << endl;
return 0;
}
```
相关推荐
![h](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)