1. 云栖社区>
  2. >
  3. 正文

CodeForces - 231C To Add or Not to Add

作者:用户 来源:互联网 时间:2018-08-29 10:48:10

思维Codeforce

CodeForces - 231C To Add or Not to Add - 摘要: 本文讲的是CodeForces - 231C To Add or Not to Add, C. To Add or Not to Add

C. To Add or Not to Add time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

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. Examples 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 array5, 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的序列和k次操作,每次操作可以使任意一个数加1,无需把所有k次操作都用完,问操作后可以得到的出现次数最多的数和次数。


思路:训练的时候想暴力,从小到大排序,遍历每一个数,找以这个数为目标可以转化多少个数。

然后果不其然超时,想了很多办法预处理求每个数朝前可以扩展的个数,网上看到一个代码,哇,茅塞顿开,简直不要太优雅。

既然预处理每个数需要扩展的大小很难,我们可以反过来求连续数的和,从而求出。

(说的可能不清楚...具体看代码吧还是)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#define max_ 100010
#define inf 0x3f3f3f3f
#define ll long long
using namespace std;

int n,k;
int num[max_];
int main(int argc, char const *argv[]) {
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    cin>>num[i];
    sort(num+1,num+1+n);
    ll sum=0;
    ll maxx=-1,ma;
    int i=1,j=1;
    for(;i<=n;i++)
    {
        sum+=num[i];
        while((num[i]*(i-j+1LL)-sum)>k)
        {
            sum-=num[j++];
        }
        if(maxx<i-j+1LL)
        {
            maxx=i-j+1;
            ma=num[i];
        }
    }
    printf("%lld %lld\n",maxx,ma);
    return 0;
}



以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索思维 Codeforce ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备