求 $\max_{1 \leq i,j\leq n } \left \{ a_i \bmod a_j \right \} $

首先一个很暴力的思路就是 $O(n^2)$ 枚举

然后我们考虑优化

对于每一个小鱼，我们可以算出它重量的倍数，然后根据这个倍数来在输入数据中找小于等于这个倍数的最大值

所以我们可以进行二分或者用一个数组进行统计

并且我们可以进行离散化更加去优化

时间复杂度 $O(n\log n)$ ？（不确定我也不会算）

#include<algorithm>
#include<iostream>
#include<cstdio>
using namespace std;
const int N=2*1e6+10;
int n,ans=0,maxn=-2e9;
int a[N],p[N];
inline int reads(){
	char c=getchar();
	int x=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return x*f;
}
signed main(){
	n=reads();
	for(int i=1;i<=n;i++){
		a[i]=reads();
		maxn=max(maxn,a[i]);
	}
	for(int i=1;i<=n;i++) ans=max(ans,maxn%a[i]);//这里其实可以不这样写，只要处理数据处理到m=maxn*2即可
	sort(a+1,a+n+1);
	n=unique(a+1,a+n+1)-a-1;
	for(int i=1;i<n;i++){
		for(int j=a[i];j<=a[i+1];j++){
			p[j]=a[i];
		}
	}
	p[a[n]]=a[n];
	for(int i=1;i<=n;i++){
		for(int j=2*a[i];j<=maxn;j+=a[i]){
			ans=max(ans,p[j-1]%a[i]);
		}
	}
	printf("%d\n",ans);
	return 0;
}

形式化题目

求 $max_{1\le i,j \le n} a_i\% a_j$

法一 20pts

$O(n^2)$ 暴力

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,a[100005],ans;

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	sort(a+1,a+n+1);
	for (int i=1;i<n;i++){
		for (int j=i+1;j<=n;j++){
			ans=max(ans,a[j]%a[i]);
		}
	}
	printf("%d",ans);
	return 0;
}

法二 正解

对于每一个小鱼，如果要使它吃的大鱼剩余的最大，

那么大鱼的重量应该是在 最接近它的一个倍数 且 比它那个倍数小

显然，红点比绿点更优

基于这个性质，我们考虑预处理数组 $pre_i$ 表示第一个 最接近$i$ 且 比$i$小 的大鱼的重量

预处理的代码如下：(应该很好理解)

sort(a+1,a+n+1);
int top=0;
for (int i=1;i<=2000000;i++){
  if (top<n && a[top+1]<i) top++;
  pre[i]=a[top];
}

接下来枚举每一个鱼作为小鱼，再枚举它的倍数， $pre_i$ 为在此情况下最优的一个大鱼，然后记录答案即可

for (int i=1;i<=n;i++){//枚举小鱼 
	for (int j=a[i];j<=2000005;j+=a[i]){//枚举倍数 
		if (pre[j]<a[i]) continue;
		ans=max(ans,pre[j]%a[i]);
	} 
}

你就惊奇地发现TLE了

是由于 $n\le 2*10^6$

又因为 $a_i\le 10^6$

考虑使用桶排序的思想存每一个鱼的重量

然后就AC了

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int n,a[2000006],pre[2000006],top,ans;
bool vis[2000006];

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d",a+i);
		vis[a[i]]=1;
	}
	sort(a+1,a+n+1);
	for (int i=1;i<=2000000;i++){
		if (top<n && a[top+1]<i) top++;
		pre[i]=a[top];
	}
	for (int i=1;i<=2000000;i++){//枚举小鱼
    if (!vis[i]) continue;
		for (int j=i;j<=2000005;j+=i){//枚举b倍数 
			if (pre[j]<i) continue;
			ans=max(ans,pre[j]%i);
		} 
	}
	printf("%d",ans);
	return 0;
}

形式化题意：找两个数取模最大。

首先，如果枚举小鱼的话，直接枚举大鱼，就超时了，所以优化。

假设这条鱼重量是 $i$ 我们可以枚举 $i$ 的 $2$ 倍、$3$倍，，，设他为 $j$ ，然后肯定是 $j$ 往左偏移得越少，最后取模越大，那我们考虑把偏移的最少的预处理出来。

sort(a+1,a+1+n);
a[n+1]=0xccfccfccfccf;
int j=1;
for(int i=1; i<=mx+mx+10; ++i) {
	while(a[j+1]<i)++j;
	b[i]=a[j];
}

$b$ 数组记录偏移最少且出现的值。

对了，最后要多处理一倍，因为有一些大的小鱼需要吃更大的大鱼，如果不这样处理，大的小鱼就不能吃更大的大鱼了。

最后

for(int i=1; i<=mx+mx; ++i) {
	if(!vis[i])continue;
	for(int j=i+i; j<=mx+mx; j+=i) {
		ans=max(ans,b[j]%i);
	}
}

注意从 $2i$ 开始，因为比 $i$ 小的鱼要吃 $i$ 而不是被 $i$ 吃。

复杂度 O(nlnn)

小鱼吃大鱼 题解

题意简述

小鱼会不断撕咬大鱼，每一口都咬下与它自身等重的肉（小鱼保持体重不变），直到大鱼剩余的体重小于这条小鱼。输出某条大鱼剩下的最大体重。

分析

10pts（去重能多得点分...吗）

纯暴力，没啥好说的。。。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+7;
int n,a[N],tong[N],near[N],ans,res,tmp,fl,maxx;
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		if(i>=2)if(a[i]!=a[i-1])fl=1;
	}
	if(n==1){
		cout<<a[1]<<'\n';
		return 0;
	}
	if(!fl){
		cout<<0<<'\n';
		return 0;
	}
	if(n<=10000){
		sort(a+1,a+1+n);
		for(int i = 1;i<=n;i++){//小鱼(吃别人)
			if(ans>=a[i]-1)continue;
			for(int j = i+1;j<=n;j++){//大鱼(被人吃)
				ans=max(ans,(a[j]%a[i]));
				if(ans>=a[i]-1)break;
			}
		}
		cout<<ans<<'\n';
		return 0;
	}
	return 0;
}

特判一下是不是只有一个鱼or所有鱼体重相等（只剩下一个，其他全都没了）。

100pts(二分)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+7;
int n,a[N],ans;
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++)cin>>a[i];
	sort(a+1,a+1+n);
	for(int i = 1;i<=n;i++) {
		int l=i,r=n;
		for (int j = 2*a[i]-1;j-a[i]<=a[n];j+=a[i]){
			while(l<r){
				int mid=(l+r+1)>>1;
				if(a[mid]==j){
					l=mid;
					break;
				}
				if(a[mid]>j)r=mid-1;
				else l=mid;
			}
			ans=max(ans,a[l]%a[i]);
		}
	}
	cout<<ans<<'\n';
	return 0;
}

来自dalaoAmy29的优化！！！

if(ans>=a[i])break;

BUT注意这样写要记得i从n到1，i--

100pts(埃筛)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+7;
int n,a[N],tong[N],near[N],ans,res,tmp,fl,maxx;
signed main(){
	cin>>n;
	for(int i = 1;i<=n;i++){
		cin>>a[i];
		tong[a[i]]=1;//这是桶（汉语拼音）
	}
    for(int i = 1;i<=N;i++){
      //预处理near[]，很明显存的是上一个有数的位置，免得虽然没有鱼还会再遍历到它，这样还得再判断
    	if(i==1)near[i]=-0x3f;
        else near[i]=tmp;
        if(tong[i])tmp=i;
    }
	for(int i = near[N];i>=1;i=near[i]){//往"前一个"找，near[]用上了
		if(res>=i)continue;//答案在这段区间里比当前的数还往后（更优）
		for(int j = 2;i*j<=N;j++)
			res=max(res,near[i*j]-i*(j-1));//找一个更大的余数
	}
	cout<<res<<'\n';
	return 0;
}

(溜