代码源R2A题解

喜欢发题解的蒟蒻

2026-08-27 16:04:34

发布于：山东

7阅读

0回复

0点赞

给大家介绍一个OJ，代码源，准备CSP-J/S，ICPC/CCPC都可以到这里面找，题目质量很可以，界面也很不错

题目

传送门
给定 $n$ 个整数 $a_1,a_2,\dots,a_n$ ，求其中最大，次大，和第三大的值的和
对于 $100\%$ 的数据， $3\le n \le 100$ ， $1 \le a_i \le 10^5$

解析

100%

对 $n$ 个数进行排序，选择最大的三个数求和即可
时间复杂度 $O(n$ $log$ $n)$ ，空间复杂度 $O(n)$
考虑能否 $O(n)$ 求最大，次大，和第三大的值，答案当然是可以的，思路如下：
定义三个变量 $firstmax$ ， $secondmax$ ， $thirdmax$
每次遇到一个数( $x$ )分为 $4$ 种情况：

$x$ 大于 $firstmax$ ，这种情况下最大值变为这个数，次大值变为之前的最大值，第三大值变为之前的第二大值，这里为了记录之前的值，要开个变量存储一下
$x$ 不符合1.但 $x$ 大于 $secondmax$ ，这种情况下最大值不变，次大值变为这个数，第三大值变为之前的第二大值，这里为了记录之前的值，同1.
$x$ 不符合1.2.但 $x$ 大于 $thirdmax$ ，这种情况下，最大值不变，次大值不变，第三大值变为这个数
$x$ 不符合1.2.3.不做处理

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$
由于 $i$ 对 $a_i$ 没有影响，所以可以滚动变量存储
时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
ll x;
ll firstmax, secondmax, thirdmax;
int main() {
    cin >> n;
    while(n--) {
        cin >> x;
        if(x > firstmax) {
            ll lastfirstmax = firstmax;
            firstmax = x;
            ll lastsecondmax = secondmax;
            secondmax = lastfirstmax;
            thirdmax = lastsecondmax;
        } else if(x > secondmax) {
            ll lastsecondmax = secondmax;
            secondmax = x;
            thirdmax = lastsecondmax;
        } else if(x > thirdmax) {
            thirdmax = x;
        }
    }
    cout << firstmax + secondmax + thirdmax;
    return 0;
}

有帮助，赞一个

去预览

0/2000

这里空空如也

题目

解析

100%

热门讨论