USACO 2021 US Open, Bronze Problem 1. Acowdemia I

Bessie the cow has enrolled in a computer science PhD program, driven by her love of computer science and also the allure of one day becoming "Dr. Bessie". Having worked for some time on her academic research, she has now published NN papers (1≤N≤1051≤N≤105), and her ii-th paper has accumulated cici citations (0≤ci≤1050≤ci≤105) from other papers in the research literature.

Bessie has heard that an academic's success can be measured by their hh-index. The hh-index is the largest number hh such that the researcher has at least hh papers each with at least hh citations. For example, a researcher with 44 papers and respective citation counts (1,100,2,3)(1,100,2,3) has an hh-index of 22, whereas if the citation counts were (1,100,3,3)(1,100,3,3) then the hh-index would be 33.

To up her hh-index, Bessie is planning to write a survey article citing several of her past papers. Due to page limits, she can include at most LL citations in this survey (0≤L≤1050≤L≤105), and of course she can cite each of her papers at most once.

Help Bessie determine the maximum hh-index she may achieve after writing this survey.

Note that Bessie's research advisor should probably inform her at some point that writing a survey solely to increase one's hh index is ethically dubious; other academics are not recommended to follow Bessie's example here.

 

 

 

SAMPLE INPUT:

4 0
1 100 2 3

SAMPLE OUTPUT:

2

Bessie cannot cite any of her past papers. As mentioned above, the hh-index for (1,100,2,3)(1,100,2,3) is 22.

 

SAMPLE INPUT:

4 1
1 100 2 3

SAMPLE OUTPUT:

3

If Bessie cites her third paper, then the citation counts become (1,100,3,3)(1,100,3,3). As mentioned above, the hh-index for these counts is 33.

 

 

Problem credits: Dhruv Rohatgi

USACO 2021 US Open, Bronze Problem 1. Acowdemia I 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Dhruv Rohatgi )

Let's suppose that L=0L=0; then we just want to compute the hh-index of Bessie's papers with no additional citations. To find this, we can sort the citation counts from largest to smallest, and find the largest hh such that the first hh papers all have at least hh citations. This can be done in one pass through the sorted counts.

Now let's consider how to use LL extra citations to increase the hh-index. Since the survey cannot cite any one paper multiple times, it's not possible to increase the hh-index by more than 11: the (h+1)(h+1)-st most cited paper before the survey had at most hh citations, so afterwards it cannot have more than h+1h+1 citations.

But it's not always possible to increase the hh-index by one. When is it possible? Well, out of the top hh papers before the survey, some kk of them have exactly hh citations (and the rest have more than hh). We need to cite each of these kk papers. Additionally, we need to cite the (h+1)(h+1)-st most cited paper. So it's necessary that L≥k+1L≥k+1. Finally, if the (h+1)(h+1)-st most cited paper has less than hh citations, then we cannot hope to increase the hh-index. Conversely, if it has hh citations (it cannot have more than hh), and if L≥k+1L≥k+1, then the hh-index can be increased to h+1h+1.

Below is Danny Mittal's code, which does a slight variation on the above idea. This program increments the citation counts of the [h−L+2,h+1][h−L+2,h+1]-most cited papers (which we've seen is optimal) and checks what the new hh-index is.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;
 
public class AcowdemiaI {
 
    static int hIndex(Integer[] papers) {
        int h = papers.length;
        while (h > 0 && papers[h - 1] < h) {
            h--;
        }
        return h;
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int l = Integer.parseInt(tokenizer.nextToken());
        Integer[] papers = new Integer[n];
        tokenizer = new StringTokenizer(in.readLine());
        for (int j = 0; j < n; j++) {
            papers[j] = Integer.parseInt(tokenizer.nextToken());
        }
        Arrays.sort(papers, Comparator.reverseOrder());
        int h = hIndex(papers);
        if (h != n) {
            for (int j = h; j >= 0 && j > h - l; j--) {
                papers[j]++;
            }
        }
        Arrays.sort(papers, Comparator.reverseOrder());
        System.out.println(hIndex(papers));
    }
}

[/hide]