2291 Rotten Ropes #2

• ref:Rotten Ropes

とりあえず、普通に解いたやつを。
テストケースごとに強度別のロープの数を計数しておいて、強度の強い側から順にテストするだけ。あと打ち切れる場合は適当に打ち切るように。

#include <iostream>
#include <map>

using namespace std;

int solve(const map<int, int>& counts, int n)
{
    typedef map<int, int>::const_reverse_iterator iterator;

    int total = 0;
    int max_score = 0;
    for (iterator it = counts.rbegin(); it != counts.rend(); ++it) {
        total += it->second;
        int score = it->first * total;
        if (it->first * n <= max_score) break;
        if (score > max_score) {
            max_score = score;
        }
    }

    return max_score;
}

void test()
{
    int n;
    cin >> n;

    map<int, int> counts;

    for (int i = 0; i < n; i++) {
        int w;
        cin >> w;
        counts[w]++;
    }

    cout << solve(counts, n) << endl;
}

int main()
{
    int t;

    cin >> t;

    for (int i = 0; i < t; i++) {
        test();
    }

    return 0;
}