Topic describes

Motivated by a love of computer science and the temptation to one day become “Dr. Bessie,” Cow Bessie began her PhD in computer science.

After a period of academic research, she has published N papers, and her first paper has received ci citation from other research literature.

Bessie had heard that academic achievement could be measured by an H-index.

The h-index is equal to the largest integer h that causes the researcher to have at least H papers with at least H citations.

For example, if a researcher has four papers with (1,100,2,3) citations, the h-index will be 2, whereas for (1,100,3,3) citations, the h-index will be 3.

To improve her H-index, Bessie plans to write a review and cite some of the papers she has written.

Due to the page limit, she can cite no more than L papers in this review, and she can only cite each of her papers no more than once.

Please help Bessie figure out the maximum H-index she can achieve after writing this review.

Note that Bessie’s supervisor might have advised her that writing a review solely to improve her H-grade was unethical; We do not recommend that other scholars emulate Bessie’s behavior.

Input format

The first line of input contains N and L.

The second line contains N space-separated integers C1,… , cN.

The output format

Output the maximum H-index that Bessie can achieve after writing the review.

Data range

1 N or less 10 ^ 5 or less,

0 or less ci 10 ^ 5 or less,

0 L or less 10 ^ 5 or less

Enter the sample

4 0
1 100 2 3
Copy the code

The output sample

2
Copy the code

Example 1 Explanation

Bessie could not cite any of the papers she had written. As mentioned above, the h index of (1,100,2,3) is 2.

Their thinking

Firstly, sort the initial number of references in ascending order, and then work out the initial H index under the current situation. The specific method is as follows:

Starting from the theoretical maximum N, start from the first element of the array, and compare. If the current value is less than the h exponent currently enumerated, the H exponent is reduced by one unit, and the array traversal continues

And then you can find the largest h-exponent in the current situation

Then you can determine if you can get to h0+1 through the current H0 (increasing the h index by one unit)

You just have to do a binary search to find the last number less than h0+1, and figure out how many additional papers you need to get to h0+1 at this right end point

Since the array is in ascending order, after calculating the required number of papers, we only need to offset the left endpoint of the same distance to have this many papers (that is, the number of references in this paragraph is all equal to h0, add one to reach h0+1).

Then cycle through, remembering to consider the limit of citations and one citation per paper

code

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    static final int N = 100010;
    static int[] c = new int[N];
    static int n, l;

    static int found(int v) {   // Binary search to find the last number less than v

        if(c[1] >= v) return -1;

        int l = 1, r = n;

        while(l < r) {
            int mid = l + r + 1 >> 1;   //+1 prevents an infinite loop
            if(c[mid] >= v) r = mid - 1;
            else l = mid;
        }

        return r;

    }

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        l = sc.nextInt();

        for(int i = 1; i <= n; ++i) c[i] = sc.nextInt();

        Arrays.sort(c, 1, n + 1);

        int h = n;  // Start with the theoretical maximum

        while(c[n - h + 1] < h--) ; // If the current enumeration does not meet the h-index standard, the standard will be lowered
        ++h;    // The top loop will subtract one more time, add back here

        int h2 = h + 1; // See if you can reach h+1

        /* The number of papers required is h2-n + found(h2). If the number of papers cited is found(h2), the h-index can be improved. So this interval has to be all H and by quoting papers from this interval you can increase the overall H index by one unit */
        while(h2 - n + found(h2) <= l && c[n - h2 + 1] == h) {
            l -= h2 - n + found(h2);    // Deduct the number of references
            h2++;   // The h index of the probe continues to rise
            h++;    // The current reachable H index also rises} System.out.println(h); }}Copy the code