To Add or Not to Add

題目描述

A piece of paper contains an array of $n$ integers $a_1,a_2,...,a_n$. Your task is to find a number that occurs the maximum number of times in this array.

However, before looking for such number, you are allowed to perform not more than $k$ following operations — choose an arbitrary element from the array and add $1$ to it. In other words, you are allowed to increase some array element by $1$ no more than $k$ times (you are allowed to increase the same element of the array multiple times).

Your task is to find the maximum number of occurrences of some number in the array after performing no more than $k$ allowed operations. If there are several such numbers, your task is to find the minimum one.

輸入格式

The first line contains two integers $n$ and $k$ ( $1<=n<=10^5$ ; $0<=k<=10^9$ ) — the number of elements in the array and the number of operations you are allowed to perform, correspondingly.

The third line contains a sequence of $n$ integers $a_1,a_2,...,a_n$ $(|a_i|<=10^9)$ — the initial array. The numbers in the lines are separated by single spaces.

輸出格式

In a single line print two numbers — the maximum number of occurrences of some number in the array after at most $k$ allowed operations are performed, and the minimum number that reaches the given maximum. Separate the printed numbers by whitespaces.

提示

In the first sample your task is to increase the second element of the array once and increase the fifth element of the array twice. Thus, we get sequence $6,4,4,0,4$, where number $4$ occurs $3$ times.

In the second sample you don’t need to perform a single operation or increase each element by one. If we do nothing, we get array $5,5,5$, if we increase each by one, we get $6,6,6$. In both cases the maximum number of occurrences equals $3$. So we should do nothing, as number $5$ is less than number $6$.

In the third sample we should increase the second array element once and the fifth element once. Thus, we get sequence $3,2,2,2,2$, where number $2$ occurs $4$ times.

題面翻譯

題目描述

給定一個長度為 $n$ 的序列 $a1$,$a2$……$an$，請你把其中一些數進行若干次 $+1$ 操作，且操作總次數不超過 $k$，使得原序列中某數出現的次數最多。求操作之后的出現最多的數和它出現的次數。

輸入

第一行兩個整數 $n,k$，即序列的長度和操作總次數。第二行為 $a1$,$a2$……$an$。

輸出

兩個整數，分別為出現最多的次數和出現最多的數。如果有多個滿足條件的數字，輸出值最小的一個。

樣例 #1

樣例輸入 #1

5 3
6 3 4 0 2

樣例輸出 #1

3 4

樣例 #2

樣例輸入 #2

3 4
5 5 5

樣例輸出 #2

3 5

樣例 #3

樣例輸入 #3

5 3
3 1 2 2 1

樣例輸出 #3

4 2

原題

Codeforces——傳送門
洛谷——傳送門

代碼

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
typedef long long ll;int main()
{ios::sync_with_stdio(0);cin.tie(0);int n, k;cin >> n >> k;vector<int> a(n + 1);for (int i = 1; i <= n; i++){cin >> a[i];a[i] += 1e9; // 由于讀入的數據存在負數，我們可以通過巧妙地補償1e9來使數組元素成為非負數}sort(a.begin(), a.end());vector<i64> s(n + 1, 0);for (int i = 1; i <= n; i++) // 前綴和s[i] = s[i - 1] + a[i];auto get_cnt = [&](int idx){// 最大次數即[left,idx]區間的最大長度// 二分leftint l = 1, r = idx;while (l < r){int mid = (l + r) / 2;// 達到idx-mid+1個a[idx]值需要補充1LL * a[idx] * (idx - mid + 1) - (s[idx] - s[mid - 1])的差值// k>=差值，則滿足條件if (k >= 1LL * a[idx] * (idx - mid + 1) - (s[idx] - s[mid - 1]))r = mid;elsel = mid + 1;}return idx - l + 1;};int max_cnt = 0;                   // 某數出現的最大次數int ans_num = -1;                  // 取到最大次數的最小數組元素for (int idx = 1; idx <= n; idx++) // 遍歷數組，確定數組中各個元素可出現的最大次數{int cur_cnt = get_cnt(idx);if (cur_cnt > max_cnt){max_cnt = cur_cnt;ans_num = a[idx];}}cout << max_cnt << ' ' << ans_num - (int)1e9 << '\n'; // 輸出時記得將補償的1e9減去return 0;
}