A piece of paper contains an array of n integers a1, a2, ..., an. 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.
Input
The first line contains two integers n and k (1 ≤ n ≤ 105; 0 ≤ k ≤ 109) — 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 a1, a2, ..., an (|ai| ≤ 109) — the initial array. The numbers in the lines are separated by single spaces.
Output
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.
Sample test(s)
input
5 3
6 3 4 0 2
output
3 4
input
3 4
5 5 5
output
3 5
input
5 3
3 1 2 2 1
output
4 2
Note
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.
題意：給你一個數列（好吧，又是數列= =），可對這個數列中的某些數加一個值，但加的總值不能超過k。求在這些操作下，使得數列中的某個數出現的次數最多。
這個題純靠yy，我們可以依次從數列中最小的數開始枚舉，但復雜度為O(n^2)，鐵定超時。但是可以優化之，大大降低復雜度。首先對數列排序，然後依次從左往右開始枚舉，那麼這裡可以有一個狀態轉移：假設當前狀態還剩余d可操作，滿足數相等的最左端的數的位置為l，那麼新加一個數num[i+1],只要比較(num[i+1]-num[i])*(i-l+1)與d的關系即可，來改變l的位置，那麼就能很快求出下一狀態。
My code：
[cpp]
//STATUS:C++_AC_78MS_400KB
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#define LL __int64
#define Max(x,y) ((x)>(y)?(x):(y))
#define Min(x,y) ((x)<(y)?(x):(y))
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define mem(a,b) memset(a,b,sizeof(a))
const int MAX=100010,INF=200000000,MOD=1000000007;
const double esp=1e-6;
int cmp(const void *a,const void *b){
return *(int*)a - *(int*)b;
}
int num[MAX];
int n;
LL k;
int main()
{
// freopen("in.txt","r",stdin);
int i,j,l,max_cou,max_num;
LL d;
while(~scanf("%d%I64d",&n,&k))
{
for(i=1;i<=n;i++)
scanf("%d",&num[i]);
qsort(num+1,n,sizeof(int),cmp);
l=1;
max_cou=1,max_num=num[1];
for(i=2;i<=n;i++){
d=(LL)(i-l)*(LL)(num[i]-num[i-1]);
k-=d;
while(k>0 && l>1 && num[i]-num[l-1]>=k){
l--;
k-=num[i]-num[l];
}
while(k<0 && l<i){
k+=num[i]-num[l];
l++;
}
if(i-l+1>max_cou){
max_cou=i-l+1;
max_num=num[i];
}
}
printf("%d %d\n",max_cou,max_num);
}
return 0;
}
