Районная олимпиада 2019-2020 информатика

Задача E. Второй максимум

Ограничение по времени:

1 секунда

Ограничение по памяти:

256 мегабайт

Вам дана последовательность $a_1, a_2...a_n$ длины $n$. Для каждого $k$ от $2$ до $n$ найдите значение второго по величине элемента среди первых $k$ элементов последовательности $a$.

Формат входного файла

В первой строке одно целое число $n$ $(1 <= n <= 10^5)$. Во второй строке $n$ целых чисел $a_1, a_2... a_n$ $(1 <= a_i <= 10^9)$.

Формат выходного файла

Выведите ответ для каждого $k$ от $2$ до $n$.

Система оценки

Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= n <= 100$. Тесты с номерами 1-3.
2. $1 <= n <= 5000$. Тесты с номерами 4-6.
3. $1 <= n <= 10^5$. Тесты с номерами 7-10.

Пример:

Вход

7
1 2 3 3 7 5 6

Ответ

1 2 3 3 5 6

Замечание

В примере:

1. $k=2$. Первые $k$ чисел $\underline{1}, 2$. Ответ $1$
2. $k=3$. Первые $k$ чисел $1, \underline{2}, 3$. Ответ $2$
3. $k=4$. Первые $k$ чисел $1, 2, \underline{3}, 3$. Ответ $3$
4. $k=5$. Первые $k$ чисел $1, 2, \underline{3}, 3, 7$. Ответ $3$
5. $k=6$. Первые $k$ чисел $1, 2, 3, 3, 7, \underline{5}$. Ответ $5$
6. $k=7$. Первые $k$ чисел $1, 2, 3, 3, 7, 5, \underline{6}$. Ответ $6$

( Aibar Kuanyshbay )

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,c; cin >> n;
	int m1 = 0, m2 = 0;
	for(int i = 0;i<n;i++){
		int x;
		cin >> x;
		if(x>m1){
			c = m1;
			m1 = x;
			m2 = c;
		}else{
			if(m2<x)
				m2 = x;
		}
		if(i>0)
			cout << m2 << ' ';
	}
	return 0;
}

C++

Copy

показать/скрыть код

#include <cstdlib>
#include <iostream>
using namespace std;
int main(int argc, char *argv[]){
    int i, n, a, max1, max2, f = 0;
    cin >> n;
    cin >> max1;
    for (i = 1; i<n; i++) {
        cin >> a;
if(f == 0){
if (a >= max1){max2 = max1;
  max1 = a;}
    else max2 = a;
            f = 1;}
    else{
            if (a >= max1)  {
                max2 = max1;
                max1 = a;
            }
            else
                if (a > max2) max2 = a;
        }

    cout << max2 <<"   ";
    }

}

C++

Copy

DELETED

показать/скрыть код

def second_max(k):
    max=c[0]
    for i in range(k):
        if c[i] >= max:
            max = c[i]
    c.remove(max)
    max = c[0]
    for i in range(k-1):
        if c[i] >= max:
            max = c[i]
    return max
b = list()
print('Введите длину последовательности')
k = int(input())
print('Введите числа последовательности через пробел')
a = list(map(int, input().split()))
for j in range(2,k+1):
    c = a.copy()
    b.append(second_max(j))
print(b)

C++

Copy

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, a[N];

int main () {
    start
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << min(a[1], a[2]) << ' ';
    int x = max(a[1], a[2]), y = min(a[1], a[2]);
    for(int i = 3; i <= n; i++) {
        if(a[i] >= x) {
            cout << x << ' ';
            y = x;
            x = a[i];
            continue;
        }
        else {
            if(a[i] >= y) {
                cout << a[i] << ' ';
                y = a[i];
                continue;
            }
            cout << y << ' ';
            continue;
        }
    }
    return 0;
}
/*

*/

C++

Copy

показать/скрыть код

n=list(map(int,input('входные числа через пробел: ').split()))
seq_num=[]# последовательность списка[i+1]
two_max=[] # список вторых наивысших чисел

for i in range(2,len(n)+1) : seq_num.append(n[0:i]) #разбил список на последовательности, добавил в list(seq_num)
for i in range(len(seq_num)):
    seq_num[i].remove(max(seq_num[i])) # удалил максимальное число
    two_max.append(max(seq_num[i])) # добавил в list(two_max) максимальное число
    print(seq_num[i],two_max[i]) # ответ

C++

Copy

показать/скрыть код

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

int n, a[N];

int main () {
    start
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cout << min(a[1], a[2]) << ' ';
    int x = max(a[1], a[2]), y = min(a[1], a[2]);
    for(int i = 3; i <= n; i++) {
        if(a[i] >= x) {
            cout << x << ' ';
            y = x;
            x = a[i];
            continue;
        }
        else {
            if(a[i] >= y) {
                cout << a[i] << ' ';
                y = a[i];
                continue;
            }
            cout << y << ' ';
            continue;
        }
    }
    return 0;
}
/*

*/

C++

Copy

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define pf push_front
#define F first
#define S second
#define ll long long
#define all(x) x.begin(), x.end()
#define pii pair<int, int>
#define unm unordered_map
#define pll pair<ll, ll>
#define speed ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define file freopen("a.txt", "r", stdin), freopen("A.txt", "w", stdout);

void solve(){
    int n;
    cin >> n;
    ll a[n];
    for(int i = 0; i < n; i++){
    	cin >> a[i];
    }
    ll m1 = max(a[0], a[1]), m2 = min(a[0], a[1]);
    cout << m2 << " ";
    for(int i = 2; i < n; i++){
    	if(a[i] >= m1){
    		ll s = m1;
    		m1 = a[i];
    		m2 = s;
    	}
    	else{
    		if(a[i] >= m2){
    			m2 = a[i];
    		}
    	}
    	cout << m2 << " ";
    }
}
int main(){
   speed;
   int t = 1;
   while(t--){
      solve();
   }
}

C++

Copy

n = int(input()) # Ввод числа n

array = list(map(int, input().split())) # Ввод списка через запятую

for k in range(2, n+1): # проход по всем отрезкам от 1 до n

temporary = array[:k]# временный список равен срезу последних k эл-ов

temporary.remove(max(temporary)) # Убираем максимальный эл-нт из списка

print(max(temporary), end=" ") # Вывод второго максимального эл-а, в строку через пробел