自动搬运

查看原文

来自洛谷，原作者为

	caohan 生命的意义是活动，没有活动，生命不如石头。人类的意义是思考，没有思考，人类不如猛兽

搬运于2025-08-24 22:33:11，当前版本为作者最后更新于2023-06-08 18:47:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

当然大模拟干过去

现实的来讲，这不可能，因为 $-10^9 \le a_i \le 10^9$ 的限制摆在这里。

但是注意到，有很小的 $n \le 10^6$ 存在，我们就想怎么通过遍历 $a$ 数组完成计算。

在 $a_i$ 和 $a_1$ 之间，一定会有一个整数上升次数（增高音量，但要是增高音量次数小于降低次数，这个数为负数），命为 $cnt$，和一个差距（就是 $a_i-a_1$ 这个值），命为 $x$。

这时，我们就能计算出一个值 $k=\frac{x}{cnt}$ 为能正好做到弹准 $a_i$ 的。

但是有两个特殊情况：

1. $cnt=0$

   可以说明此音符在 $x=0$ 的时候一定可以弹准，进行记录。

2. $\left \lfloor k \right \rfloor \ne k$ 或者 $|k| \ne k$

   说明 $k$ 违背了题目中非负整数的要求，这个音符不可能弹准,直接抬走

一边处理，一边用 map 进行统计（空间比直接开桶小）。之后在找到最大，和那些固定能弹出的加起来就是第一问的答案，而找出这个答案的下标 $k$ 为第二问答案。

代码

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int a[1000005];
map <int,int> b;
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}//输入
	int cnt=0,ans=1,maxx=0,k=1;//初始化
	for(int i=2;i<=n;i++)
	{
		if(a[i]>a[i-1])cnt++;
		if(a[i]<a[i-1])cnt--;//统计更改次数 
		if(!cnt)
		{
			if(a[1]==a[i])
			{
				ans++;
			}
			continue;
		}//得零时进行特判
		int x=(a[i]-a[1]);
		if((a[i]-a[1])%cnt)
		{
			continue;
		}//要是有余数（除出来是小数），那就抬走
		int t1=((a[i]-a[1])/cnt);
		b[((a[i]-a[1])/cnt)]++;//往map上统计
		if(b[((a[i]-a[1])/cnt)]>maxx&&k>=0)
		{
			maxx=b[((a[i]-a[1])/cnt)];
			k=((a[i]-a[1])/cnt);
		}//超过最大就更新
	}
	cout<<maxx+ans<<"\n"<<k;
	return 0;
}