加减（双指针+前缀和）

秒速五厘米 2022-09-10 05:16 33阅读 0赞

题目：给定一个长度为n的序列，进行加一减一的操作不超过k次，最多有多少个数相同？

思路：维护若干个区间，每个区间都能在k步内变为同一个数，求最长的区间。尽量往中位数靠。

两个问题：感觉有点像 O(n^2) ；而且偶数的时候，中位数默认是中间左边的数。

#include <iostream>
    #include <algorithm>
    using namespace std;
    #define ll long long 
    const int N = 1e5 + 10;
    
    ll n, k, a[N], s[N];
    
    bool judge(ll mid, int i, int j)
    { 
    	ll tmp = a[mid];
    	
    	ll l = (mid-i) * tmp - (s[mid-1]-s[i-1]); // 从中位数到左端点 * 中位数与他们的差值 - 原本的数 = 左边需要操作的步数
    	
    	ll r = s[j]-s[mid-1] - (j-mid+1) * tmp;  // 右边也是同样的道理
    	
    	if(l + r <= k ) return true;
    	
    	return false;
    }
    
    
    int main()
    { 
    	cin >> n >> k;
    	
    	for(int i = 1; i <= n; i++) cin >> a[i];
    	
    	sort(a+1, a+1+n);
    	
    	for(int i = 1; i <= n; i++) s[i] = s[i-1] + a[i];
    	
    	int ans;
    	
    	for(int i = 1, j = 1; i <= n; i++)
    	{ 
    		ll mid = (i+j+1) >> 1;
    		
    		while(j <= n and judge(mid, i, j))
    		{ 
    			j++;
    			
    			mid = (i+j+1) >> 1;
    		}
    		ans = max(ans, j-i);
    	}
    	cout << ans << endl;
    	
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，33人围观）

还没有评论，来说两句吧...

相关阅读

相关指针的加减算术运算-指针加常数意味着什么？

一、重点 1. 指针是一个大小固定为4个byte的变量，不管是什么类型的指针大小都是固定的，它存放的只是一个地址信息。 2. 指针变量加1，即表示指针变量...

ゞ浴缸里的玫瑰/ 2024年04月18日 15:07/ 0 赞/ 86 阅读

相关进一步理解指针2：双指针、指针数组和数组指针

**目录** 目录 1 1. 概念 1 1.1. 双指针 1 1.2. 指针数组 1 1.3. 数组指针 1 2. 区别 2 3. 兼容性 2 4. 为...

傷城~/ 2024年04月18日 11:08/ 0 赞/ 73 阅读

相关 C++ 指针的加减运算

首先明确几点： 1：涉及到数组的指针，若两指针指向的不是同一个数组，那么指针之间的加减运算是无意义的，因为得到的结果就是他们地址之间的差值。 2：指针变量加/减一个整数，

Myth丶恋晨/ 2023年10月17日 12:22/ 0 赞/ 43 阅读

相关双指针

- (void)viewDidLoad { [super viewDidLoad]; //定义的指针叫做双指针

港控/mmm°/ 2023年10月17日 05:23/ 0 赞/ 40 阅读

相关 C语言指针使用例（指针自加自减运算、数组与指针、字符串与指针）

1.在一个已按升序排列的数组中插入一个数，插入后，数组元素仍按升序排列 include<stdio.h> define N 10 void fun(i

布满荆棘的人生/ 2023年07月02日 10:24/ 0 赞/ 36 阅读

相关数量加减

[https://blog.csdn.net/qq\_30932479/article/details/77280476][https_blog.csdn.net_qq_309

太过爱你忘了你带给我的痛/ 2023年06月03日 05:59/ 0 赞/ 36 阅读

相关指针的算术运算(加、减、比较、赋值、自增、自减)

1. 指针的算术运算简介: ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZ

淡淡的烟草味﹌/ 2023年01月20日 08:06/ 0 赞/ 68 阅读

相关加减（双指针+前缀和）

题目：给定一个长度为n的序列，进行加一减一的操作不超过k次，最多有多少个数相同？思路：维护若干个区间，每个区间都能在k步内变为同一个数，求最长的区间。尽量往中位数靠。两

秒速五厘米/ 2022年09月10日 05:16/ 0 赞/ 34 阅读

相关【前缀自增/减++i】和【后缀自增/减i++】的区别

> 前缀自增/减前缀自增/减会先运算后传值。这里的运算指的是该数本身自增+1或者自减-1。 > 后缀自增/减后缀自增/减会先传值后运算。 \

矫情吗；*/ 2022年06月08日 12:20/ 0 赞/ 283 阅读

相关指针自加自减运算

指针的自加自减运算不同于普通变量，并非简单的加1减1。举例： include<stdio.h> include<stdlib.h> / 指针自加自减运

墨蓝/ 2022年03月31日 08:49/ 0 赞/ 320 阅读