游游的数组染色

[题目链接](https://www.nowcoder.com/practice/d0733785b73f4430aa735d15452b72ab)

思路

给定数组，选择若干元素涂黑，得分为 黑色数字的最小值 + 黑色数字的个数，求最大得分。

关键观察

假设我们选了 个数，为了让最小值尽可能大，一定选最大的 个数。将数组降序排序后，选前 个，最小值就是 ，得分为 。

算法

1. 将数组降序排序。
2. 枚举 ，计算 ，取最大值即可。

时间复杂度 ，瓶颈在排序。

代码

C++

#include <bits/stdc++.h>
using namespace std;
int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        vector<int> a(n);
        for(int i=0;i<n;i++) scanf("%d",&a[i]);
        sort(a.begin(),a.end(),greater<int>());
        long long ans=0;
        for(int k=1;k<=n;k++){
            long long score=(long long)a[k-1]+k;
            if(score>ans) ans=score;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine().trim());
        StringBuilder sb = new StringBuilder();
        while (t-- > 0) {
            int n = Integer.parseInt(br.readLine().trim());
            StringTokenizer st = new StringTokenizer(br.readLine().trim());
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = Integer.parseInt(st.nextToken());
            Arrays.sort(a);
            long ans = 0;
            for (int k = 1; k <= n; k++) {
                long score = (long) a[n - k] + k;
                if (score > ans) ans = score;
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}