游游的数组染色

[编程题]游游的数组染色

热度指数：620 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

游游有一个长度为 $n$ 的数组 $a$ ，初始时所有元素都是白色的，游游希望选择一些数字涂黑，他的得分计算为：黑色数字的最小值 $+$ 黑色数字的个数。

请你帮他算算，他最高可以得到多少分吧。

输入描述:

每个测试文件内都包含多组测试数据。
第一行一个正整数 ，表示测试数据的组数。
接下来对于每组测试数据，输入包含两行。
第一行一个正整数 ，表示数组 的长度。
第二行  个整数 ，表示数组 。
（保证所有测试数据中  的总和都不超过 。）

输出描述:

输出  行，每行一个整数表示答案。

示例1

输入

1
5
3 5 4 2 2

输出

说明

可以选择涂黑所有数字，得分为  最大。

算法知识视频讲解

查看答案及解析

已注销

先将数组排序，暴力枚举最小数字下标i，要让黑色数量尽可能的多，那么个数就可以把所有大于等于x这个数字染成黑色，即为n - i（下标从0开始）

#include <bits/stdc++.h>

using namespace std;

signed main() {
    int _ = 1;
    cin >> _;

    while (_ -- ) {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &e : a) cin >> e;

        sort(a.begin(), a.end());

        int ma = 0;

        for (int i = n - 1; i >= 0; i--) {
            ma = max(ma, a[i] + n - i);
        }

        cout << ma << '\n';
    }

    return 0;
}

发表于 2025-07-18 17:44:47 回复(0)