哪些网站是php做的,天津企业网站建设公司,青柠海报设计网站,营销型网站的作用正题 题目大意 nnn个数#xff0c;求一对(i,j)(i,j)(i,j)要求最大化max{ai,aj}%min{ai,aj}max\{a_i,a_j\}\% min\{a_i,a_j\}max{ai,aj}%min{ai,aj} 解题思路
我们考虑枚举小的那一个iii#xff0c;显然在ki∼k(i1)−1ki\sim k(i1)-1ki∼k(i1)−1这段范围都是要减去一…正题 题目大意
nnn个数求一对(i,j)(i,j)(i,j)要求最大化max{ai,aj}%min{ai,aj}max\{a_i,a_j\}\% min\{a_i,a_j\}max{ai,aj}%min{ai,aj} 解题思路
我们考虑枚举小的那一个iii显然在ki∼k(i1)−1ki\sim k(i1)-1ki∼k(i1)−1这段范围都是要减去一个kikiki。RMQRMQRMQ查询最大值即可。
时间复杂度O(nlogn)O(n\log n)O(nlogn) codecodecode
#includecstdio
#includecstring
#includealgorithm
#includecctype
using namespace std;
const int N1e6;
int read() {int x0,f1; char cgetchar();while(!isdigit(c)) {if(c-)f-f;cgetchar();}while(isdigit(c)) x(x1)(x3)c-48,cgetchar();return x*f;
}
int n,ans,lg[N10],f[N10][21];
int get_min(int l,int r){if(rN)rN;int zlg[r-l1];return max(f[l][z],f[r-(1z)1][z]);
}
int main()
{
// freopen(data.txt,r,stdin);nread();for(int i2;iN;i)lg[i]lg[i1]1;for(int i1;in;i){int xread();f[x][0]x;}for(int j1;j20;j)for(int i1;i(1j)-1N;i)f[i][j]max(f[i][j-1],f[i(1(j-1))][j-1]);for(int i1;iN;i)if(f[i][0]){for(int ji;jN;ji)ansmax(ans,get_min(j,ji-1)-j);}printf(%d,ans);
}
