---

C. To Add or Not to Add

原创 于 2023-09-04 14:19:24 发布 · 粉丝可见 · 253 阅读 · 0 · 0 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/132667739

题目：

样例1：

cobol<br/>5 3<br/>6 3 4 0 2<br/>

3 4

样例2：

cobol<br/>3 4<br/>5 5 5<br/>

3 5

样例3：

cobol<br/>5 3<br/>3 1 2 2 1<br/>

4 2

思路：

贪心题目，化分离数为块。这里要注意的是  需要进行的排序

以及操作的过程是什么样子的。    感觉那些操作数的问题都是  需要进行排序，然后 根据排序后的数值之差就是操作次数，  (i - j + 1)  （类似题目： 交换字符）最后 乘以 a[i] 就是将 a[i] 作为目标，然后 - sum 是判断操作次数是否符合规定的操作次数 k 。 如果不符合那么 丢弃前面的选择的元素，所以 j++

代码详解如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define ___G std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
int n,k;

vector<int>a;	// 存储数组

using PII = pair<int,int>;


inline void solve()
{
	cin >> n >> k;
	
	for(int i = 0,x;i < n;++i)
	{
		cin >> x;
		a.emplace_back(x);
	}
	
	// 从小到大的排序。		感觉操作数类的题目都是  需要排一遍数
	// 然后根据位置的下标之差就是需要操作的数，（类似题目： 交换字符）
	// 根据元素位置之差，就是需要添加的数
	sort(All(a));
	
	int sum = 0;	// 选取的操作元素
	
	PII ans = {0,0};	// ans.x 总数  ans.y 为 众数
	
	for(int i = 0,j = 0;i < n;++i)
	{
		// 开始选取
		sum += a[i];
		
		// 这里 i - j + 1 是指操作次数
		// * a[i]  这里乘以 a[i] 就是对选取的数值进行操作
		// - sum 就是统计有效的操作数,如果 > k 说明超出了操作数
		// 丢弃前面先选择的 小的数 
		while((i - j + 1) * a[i] - sum > k) sum -= a[j++];
		
		// 如果操作后的该元素的众数比之前的多，那么更新答案
		if(ans.x < (i - j + 1)) ans = {i - j + 1,a[i]};
	}
	
	cout << ans.x << ' ' << ans.y << endl;
	
}


signed main()
{
//	freopen("a.txt", "r", stdin);
	___G;
	int _t = 1;
//	cin >> _t;
	while (_t--)
	{
		solve();
	}

	return 0;
}

最后提交：