如何做网站百度排名优化/哈尔滨网络优化推广公司

题目链接：

暴力思路：

我们通过 DFS 枚举所有的方案，在对每个方案进行判断。因为我们是从小到大开始枚举的，所以如果这个方案的 S 大于了我们维护的最大值，我们就更新最大值，在更新方案。这种做法的时间复杂度为 0(n^3)，只能通过 30% 的样例。

暴力代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+20;int n, arr[N];
int ans[N]; //每次存组合数
int res[N], r;//查找两个数最小公倍数
int find(int x, int y){return x*y / __gcd(x, y);
}void dfs(int x, int start){if(x > 3){//求s的最大值int a = find(ans[1], ans[2]);int b = find(ans[2], ans[3]);int c = find(ans[1], ans[3]);int p1 = find(min(min(a, b),c), max(max(a,b),c));int p2 = ans[1] * ans[2] * ans[3];int s = p2*p1/(a*b*c);if(s > r){r = s;//更新最大 S 的方案for(int i =1; i <= 3; i++){res[i] = ans[i];}}return;}for(int i = start; i <= n; i++){ans[x] = arr[i];dfs(x+1, i+1);ans[x] = 0;}
}signed main(){cin >> n;for(int i = 1; i <= n; i++) cin >> arr[i];//排序sort(arr+1, arr+1+n);dfs(1, 1);for(int i =1; i <= 3; i++) cout << res[i] << " ";return 0;
}

优化思路：

对S公式的推导视频。

通过对式子的推导，我们知道了，要求 s  的最大值，就转换为找到三枚宝石的最大公因数。

①我们可以先预处理，对 1~1e5+100 的所有数字，找到每个数字的所有公因数，将每个数的所有公因数都存在 vector 中。

②在读入数据，用 cnt 数组记录每个数字的所有公因数出现的次数，我们要找的出现次数大于 3 的最大公因数 k 。

③枚举读入的数据，如果这个数能被最大公因数 k  整除，我们用 ans 容器来记录所有的答案。

④输出答案，我们输出 ans 容器中的前面三个数字， 这就是最小的方案。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;int n, arr[N];
//该数组中存得是 1~N 中每个数得所有公因数
vector<int> q[N];
//该数组中存得是 数据 中每个数 公因数出现的次数
int cnt[N];
//出现个数大于3的最大公因数
int k;
//该数组存的是数据中能被最大公因数整除的所有答案
vector<int> ans;signed main(){cin >> n;//先对 1~N 预处理，找到每个数的所有公因数for(int i = 1; i<= N; i++){//保证每次将得都是 i 得倍数for(int j = i; j <= N; j+=i){//将 j 得公因数全部存入到 q[j]中q[j].push_back(i);}}//读入数据for(int i = 1; i <= n; i++){cin >> arr[i];for(auto x: q[arr[i]]){//公因数出现的次数加1cnt[x] ++;}}// 在 cnt 中找到出现个数大于3 的最大公因数for(int i = 1; i <= N; i++){if(cnt[i] >= 3){k = i;}}//对数组排序sort(arr+1, arr+1+n);//在数组中找到能被最大公因数整除的数， 并将它存入到 ans 中找到出现个数大于3for(int i = 1; i <= n; i++){if(arr[i] % k == 0){ans.push_back(arr[i]);}}//输出ans数组中的前面三个答案for(int i = 0; i < 3; i++){cout  << ans[i]<< " ";}return 0;
}