Решение задачи Стрельба с Codeforces

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

Вася недавно начал тренироваться стрельбе из пистолета. Сегодня тренер предложил ему следующее задание. Он выставил на стол n банок в ряд. Банки пронумерованы слева направо от 1 до n. Чтобы выполнить задание, Васе предстоит сбить каждую из банок ровно по одному разу. При этом порядок, в котором Вася будет сбивать банки, он выбирает самостоятельно.

Вася знает, что прочность i-й банки равна ai. Это значит, что если Вася уже сбил x банок и сейчас начнет стрелять в i-ю банку, то, чтобы сбить эту банку, ему понадобится (ai⋅x+1) выстрел. Считайте, что если Вася начал стрелять в банку номер i, то он будет стрелять в нее, пока он ее не собьет.

Определите такой порядок стрельбы по банкам, что Вася сделает минимально возможное количество выстрелов, чтобы сбить каждую из n банок ровно по одному разу.

Код 

#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int n, temp, res = 0;
    cin >> n;
    vector<int> a, b;
    for(int i = 0; i < n; ++i){
        cin >> temp;
        a.push_back(temp);
    }
    b = a;
    sort(a.begin(),a.end());
    reverse(a.begin(), a.end());
    for(int i = 0; i < a.size(); ++i){
        res+=a[i] * i + 1;
    }
    cout << res << endl;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            if(a[i] == b[j]){
                cout << j + 1<< " ";
                b[j] = 0;
            }
        }
    }
    return 0;
}

         

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




Комментарии

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


© 2020 mycod   [email protected]  Карта сайта   Правообладателям