怎么看网站的外链,网站设计与制作说明,四川阿坝建设招标网站,代理招生平台题目链接#xff1a;https://www.lanqiao.cn/problems/3525/learning/
个人评价#xff1a;难度 2 星#xff08;满星#xff1a;5#xff09; 前置知识#xff1a;调和级数 整体思路
题目描述不严谨#xff0c;没说在无解的情况下要输出什么#xff08;比如 n n n …题目链接https://www.lanqiao.cn/problems/3525/learning/
个人评价难度 2 星满星5 前置知识调和级数 整体思路
题目描述不严谨没说在无解的情况下要输出什么比如 n n n 个 1 1 1所以我们先假设数据保证有解从 2 2 2 到 1 0 6 10^6 106 枚举 x x x 作为约数对于约数 x x x 去扫所有 x x x 的倍数总共需要扫 n 2 n 3 n 4 ⋯ n n ≈ n ln n \frac{n}{2}\frac{n}{3}\frac{n}{4}\cdots\frac{n}{n}\approx n\ln n 2n3n4n⋯nn≈nlnn 次取所有 x x x 的倍数在原数组中的下标这些下标对应的数字一定同时包含 x x x 这个约数取这些下标中最小的两个 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2就是满足题意的以 x x x 为约数的两个数的下标最后对所有约数 x x x 取最满足题意的 i d x 1 , i d x 2 idx_1,idx_2 idx1,idx2 即可如果存在多组 i , j i,j i,j请输出 i i i 最小的那组。如果仍然存在多组 i , j i,j i,j请输出 i i i 最小的所有方案中 j j j 最小的那组。
过题代码
#include bits/stdc.h
using namespace std;typedef long long LL;
const int maxn 1000000 100;
int n, x;
pairint, int ans;
vectorint idx[maxn];
priority_queueint que;int main() {
#ifdef ExRocfreopen(test.txt, r, stdin);
#endif // ExRocios::sync_with_stdio(false);cin n;ans {n 1, n 1};for (int i 1; i n; i) {cin x;idx[x].push_back(i);}for (int i 1; i maxn; i) {sort(idx[i].begin(), idx[i].end());while (idx[i].size() 2) {idx[i].pop_back();}}for (int i 2; i maxn; i) {while (!que.empty()) {que.pop();}for (int j i; j maxn; j i) {for (int k 0; k idx[j].size(); k) {que.push(idx[j][k]);if (que.size() 2) {que.pop();}}}if (que.size() 2) {continue;}int r que.top();que.pop();int l que.top();que.pop();if (l ans.first) {ans {l, r};} else if (l ans.first) {if (r ans.second) {ans {l, r};}}}cout ans.first ans.second endl;return 0;
}
