Решение задачи "Максимальная медиана" с Codeforces

Без пояснения   Просмотров: 29


Вам дан массив a из n целых чисел, где n нечётно. Вы можете проделать с массивом следующую операцию:

Выбрать один из элементов массива (например ai) и увеличить его на 1 (то есть заменить на ai+1).
Вы хотите сделать медиану массива максимально большой, используя не более k операций.

Медианой нечётного по размеру массива называется средний элемент, если массив отсортировать по неубыванию. Например, медианой массива [1,5,2,3,5] является 3.

Код

#include<bits/stdc++.h>
using namespace std;
long long n,m,k,a[400000],ans,l;
int main()
{
	cin >> n >> k;
	m = n / 2;
	for(int i = 0; i < n;i++)
		cin >> a[i];
	sort(a, a + n);
	a[n] = 3e9;
	ans = a[m];
	for(int i = m; i <= n; i++){
		l = i - m + 1;
		if(l * (a[i + 1] - a[i]) <= k){
			k -= l * (a[i + 1] - a[i]);
			ans += a[i + 1] - a[i];
		}
		else{
			ans += k / l;
			cout << ans;
			return 0;
		}
	}
	cout << "ERROR";
}

         


<div style=

A PHP Error was encountered

Severity: Notice

Message: Undefined index: first_name

Filename: templates/tasksdecision_view.php

Line Number: 133

Backtrace:

File: /var/www/u0984434/data/www/hsecodes.com/application/views/templates/tasksdecision_view.php
Line: 133
Function: _error_handler

File: /var/www/u0984434/data/www/hsecodes.com/application/controllers/Tasksdecision.php
Line: 120
Function: view

File: /var/www/u0984434/data/www/hsecodes.com/index.php
Line: 315
Function: require_once

Администратор Photo" /> Автор:


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться