自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

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

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

以下是正文

题目大意：

从这些点中找出最大的点，然后再在周围的点都加上$1$ 。

$m$次操作后输出最大值点的编号。

一些小小的性质：

很显然，如果直接按照题目中所说的那么很明显的会$T$飞（某位学长亲测）。

1. 很显然，手玩几个东西就会发现，其实就是两个点（哪两个点，先留个悬念）在那里跳啊跳啊，跳啊跳啊，我的骄傲放纵。

2. 那么具体怎么跳呢？

我们先找到一开始最优秀的点呀 。

• 最大的点中编号最小的点。

emmm大概就是这样操作的。。。

for(int i=1;i<=n;i++) {
	a[i]=re();
	if(a[i]>maxx) {
		maxx=a[i];
		now=i;
	}
}

然后就建边先找到这个最大点的最大值的位置。

好了！悬念解开了!

没错就只需要看最大值的点和最大点的最大值点就好了呀。

因为+1+1+1只更新了这些点周围的点的好感值，所以最大点的最大值点是最有可能更新称为最大值。

关于这个点位置的处理

int maxn=0; int k=0;
for(int i=fir[now];i;i=nex[i])
{
	int p=poi[i];
	if(a[p]>maxn||(a[p]==maxn&&p<k)) {
		maxn=a[p];
		k=p;
	}
}

下面就是重头戏了嗷！！

1. 如果直接没有进循环，特判一手。

那么就是一个点了呀，直接输出这个点他不香吗，他香的一批!

于是剩下的就是判断这两个最大点的最大点的最大值的差值就好了

2. 如果差值比$m$天大，就说明天数不够去让那个东西更新成为最大值。

——直接输出最大点就可以了.

3. 如果刚好相等呢？？？

刚好更新出来最大值，就要看编号了来比较，输出编号更小的那个就好了。

4. 如果更新到最大值之后，继续跳的时候。

如果奇数的话那么就跳到了这两个点编号更大的点。

偶数的时候就是另一个点了呀。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#define int long long 
#define N 5000010
using namespace std;
int re() {
	int p=0; char i=getchar();
	while(i<'0'||i>'9')	i=getchar();
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return p;
}
int t,n,m,sum,now;
int a[N];
int fir[N],nex[N],poi[N];
void ins(int x,int y) {       //某些大佬说不需要建边,我太菜了
	nex[++sum]=fir[x];
	poi[sum]=y;
	fir[x]=sum;
}
void Clear() {					//t次询问清0,建图只需要清空fir,sum记得清0
	memset(fir,0,sizeof(fir));
	memset(a,0,sizeof(a));
	sum=0; now=0; 
}
signed main()
{
	t=re();
	while(t--)
	{
		Clear();
		n=re();m=re();
		int maxx=0;
		for(int i=1;i<=n;i++) {
			a[i]=re();
			if(a[i]>maxx) {			//不能等于,因为这样才是编号最小的
				maxx=a[i];
				now=i;
			}
		}
		for(int i=1;i<n;i++)
		{
			int a,b;
			a=re();b=re();
			ins(a,b); ins(b,a);
		}
		int maxn=0; int k=0;
		for(int i=fir[now];i;i=nex[i])
		{
			int p=poi[i];
			if(a[p]>maxn||(a[p]==maxn&&p<k)) {	同上
				maxn=a[p];
				k=p;
			}
		}
        if(k==0)    {
            printf("%lld\n",now);
            continue;
        }
		int dat=maxx-maxn;
		if(dat>m) {
			printf("%lld\n",now);
			continue;
		}
		if(dat==m) {
			printf("%lld\n",min(now,k));
			continue;
		}
		if((m-dat)&1) {					//x&1判断是否是奇数
			printf("%lld\n",max(now,k));
			continue;
		}
		else {
			printf("%lld\n",min(now,k));
			continue;
		}
	}
    return 0;
}

就酱，如果有什么不妥的地方，十分期望大家私信我

Orz