加减

加减

https://ac.nowcoder.com/acm/contest/20960/1028

链接:https://ac.nowcoder.com/acm/contest/20960/1028
来源:牛客网

题目描述

小红拿到了一个长度为 n n\n  的数组。她每次操作可以让某个数加 1 或者某个数减 1 。
小红最多能进行 k k\k  次操作。她希望操作结束后,该数组出现次数最多的元素次数尽可能多。
你能求出这个最大的次数吗?

输入描述:

第一行两个正整数 n n\n k k\k  第二行有 n n\n  个正整数 ai a_i\ai  1≤n≤1051 \leq n \leq 10^51n105 1≤k≤10121 \leq k \leq 10^{12}1k1012 1≤ai≤1091 \leq a_i \leq 10^91ai109 

输出描述:

不超过 k k\k  次操作之后,数组中可能出现最多次数元素的次数。
示例1

输入

复制 5 3 6 3 20 8 1
5 3
6 3 20 8 1

输出

复制 2
2
本题是一个枚举的问题,根本问题在于如何枚举能在有限的时间内将正确答案枚举出来,首先需要知道这个出现次数最多的数一定是序列里面某个数。在这里采用枚举左边下标,二分求右边下标的方式去提升速度(既然二分就得排序,在这里从小到大)。
既然采用区间寻找的方式去枚举,那么就需要去验证在该区间里面是否能够满足最小的变化大小小于k的要求。要想验证首先得明白在一个从小到大的序列里面,要想全部变到相同的数并且移动的大小最小那么就一定是位于中间的数,对于中间数有两个的序列来说选取哪一个都是一样的结果。然后将这个区间从中间分隔来分别去求需要移动的大小(通过前缀和的配合快速求出)。由此遍历结束取最大值就是最后的结果。
代码:
//枚举一个l,通过二分快速寻找一个r
typedef long long ll;
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 100000+10;
ll a[MAXN];
ll sum[MAXN];
ll n, k;
int check(ll l, ll r) {
    ll mid = (l+r)>>1;
    ll ans = a[mid]*(mid-l+1)-(sum[mid]-sum[l-1])+(sum[r]-sum[mid])-a[mid]*(r-mid);
    if (ans<=k) {
        return 1;
    }
    return 0;
}

int main() {
    cin>>n>>k;
    for (int i=1;i<=n;i++) {
        cin>>a[i];
    }
    sort(a+1, a+n+1);
    for (int i=1;i<=n;i++) {
        sum[i] = sum[i-1]+a[i];
    }
    ll ans = -1;
    for (ll i=1;i<=n;i++) {
        ll l = i, r = n;
        ll cnt = -1;
        while (l<=r) {
            ll mid = (l+r)>>1;
            if (check(i, mid)) {
                cnt = max(cnt, mid-i+1);
                l = mid+1;
            } else {
                r = mid-1;
            }
        }
        ans = max(ans, cnt);
    }
    cout<<ans;
    return 0;
}


全部评论

相关推荐

昨天 13:43
门头沟学院 Java
longerluck...:我猜说的是“你真**是个天才”
投递美团等公司10个岗位
点赞 评论 收藏
分享
07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务