Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
ЯрославМуравьев
0 / 0 / 0
Регистрация: 12.10.2018
Сообщений: 23
1

Максимизировать среднюю силу своей команды

05.02.2019, 00:03. Просмотров 928. Ответов 1
Метки нет (Все метки)

Здравствуйте! Проблема с алгоритмом, все никак не могу сделать, чтобы сходились ответы.
А вот и текст:

Средняя сила супергероев

У каждого супергероя есть сила, выраженная целым числом. Команда мстителей хочет максимизировать среднюю силу супергероев команде, выполняя следующие операции.

Изначально в команде n супергероев с силами a1,a2,…,an, соответственно. За одну операцию можно убрать супергероя из команды (если сейчас их не меньше двух) или увеличить силу одного супергероя на 1. Можно выполнить не более m операций. Кроме того, нельзя увеличивать силу одного супергероя больше, чем в k операциях.

Помогите мстителям максимизировать среднюю силу своей команды.

Входные данные
Первая строка содержит три целых числа n, k и m (1≤n≤105, 1≤k≤105, 1≤m≤107) — количество супергероев, максимальное количество раз, которое можно увеличивать силу одного супергероя, и общее максимальное число операций.

Вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤106) — начальные силы супергероев в команде мстителей.

Выходные данные
Выведите одно число — максимально возможную итоговую среднюю силу супергероев в команде мстителей.

Примеры
входные данные
2 4 6
4 7
выходные данные
11(у меня выходит 10)
входные данные
4 2 6
1 3 2 3
выходные данные
5 (у меня выходит 2)
Примечание
В первом примере максимальная средняя сила достигается удалением первого супергероя и увеличением силы второго супергероя на четыре.

Во втором примере один из способов достичь максимальное среднее является удаление первого и третьего супергероев и увеличением сил второго и четвертого супергероев на 2.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
using namespace std;
void sort(int n, int a[]){
    for(int i = 1; i < n; ++i)
    {
        for(int r = 0; r < n-i; r++)
        {
            if(a[r] < a[r+1])
            {
                int temp = a[r];
                a[r] = a[r+1];
                a[r+1] = temp;
            }
        }
    }
}
int main(){
    int n, k, m, sum = 0;
    cin >> n >> k >> m;
    int a[n];
    for(int i = 0; i!=n ;i++){
        int b;
        cin >> b;
        a[i]=b;
    }
    int min = 10000, min2 = 10000;
    for(int i = 0; i!=n ;i++){
        if(a[i] < min)
            min = a[i];
        if(a[i] > min && a[i] < min2)
            min2 = a[i];
        else
            continue;
    }
    if(n==2){
        sort(n,a);
        for(int i = 0; i!= k - n + 1; i++)
            a[0] = a[0] + 1;
        cout << a[0];
    }else{
        sort(n,a);
        int c = 0;
        for(int i = 0; i!=n ;i++){
            if(a[i] == a[i+1])
                c++;
        }
        if(c!=0){
            for(int i = 0; i!=k + c - n; i++){
                a[0] = a[0] + 1;
            }
            for(int i = 0; i!=c ;i++){
                sum = sum + a[i];
            }
            cout << sum/c;
        } else{
            for(int i = 0; i!= k - n + 1; i++)
            a[0] = a[0] + 1;
            cout << a[0];
        }
    }
}
Заранее спасибо)
0
Лучшие ответы (1)
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.02.2019, 00:03
Ответы с готовыми решениями:

Найти среднюю силу
Всем привет, не могу сообразить как решить задачку: Найдите среднюю силу Fcp, действующую на...

Найти среднюю силу удара
теннисный мяч летел с имп п1, когда теннисист нанес по нему удар длительностью тау=0,1 с....

Определить среднюю электромагнитную силу
Приветствую! Мне выдали задачу, решение для которой нужно запрограммировать, а я даже не знаю, в...

Найти среднюю силу сопротивления
Пуля массой 10 г, летевшая горизонтально со скоростью 600 м/с, попадает в свободно подвешенный...

Найти среднюю силу удара
6) Теннисный меч летел с импульсом р1 в горизонтальном направлении , когда теннисист произвел по...

1
ReDoX
439 / 327 / 170
Регистрация: 01.07.2015
Сообщений: 1,162
05.02.2019, 20:59 2
Лучший ответ Сообщение было отмечено ЯрославМуравьев как решение

Решение

Что-то вы нагромоздили... алгоритм следующий:

1. Посчитать ответ на отрезке [l, r];
2. ++l;
3. Если r - l > 0, пункт 1, иначе конец.

Судя по разбору, код следующий (проходит тесты):

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long int
 
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cout.precision(9);
 
  int n;
  int k;
  int m;
  cin >> n >> k >> m;
 
  vector<int> a(n);
 
  int sum = 0;
 
  for (auto& i : a) {
    cin >> i;
 
    sum += i;
  }
 
  sort(a.begin(), a.end());
 
  double ans = (sum + min(m, n * k)) / static_cast<double>(n);
 
  for (int i = 1; i < min(m + 1, n); ++i) {
    sum -= a[i - 1];
 
    ans =
        max(ans, static_cast<double>(sum + min(m - i, (n - i) * k)) / (n - i));
  }
 
  cout << fixed << ans;
}
1. Считаем префиксную сумму
2. Вычисляем ответ, когда у нас все супергерои - то есть мы не удалили ни одного
3. Вычисляем ответ для всех оставшихся случаев. То есть на каждом шаге цикла мы сокращаем кол-во супергероев на 1 и считаем ответ для оставшихся.

P.S. Не знаю, почему в min(m + 1, n) именно m + 1, но так работает... если оставить m, то валится на 6 тесте
1
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.02.2019, 20:59

Найти среднюю силу удара
Теннисный мяч летел с импульсом p1 в горизонтальном направлении, когда теннисист произвел по мячу...

Определите среднюю силу удара
Текст задачи: Мяч массой т = 300 г упал с высоты Н —1,23 м на асфальт и подскочил на ту же высоту....

Определить среднюю силу удара
Шарик массой m падает с высоты h на горизонтальную поверхность. Приняв длительность удара равной t,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.