题目链接
题解：显然，如果做两次lcm，就可以得到可能的最大解（取2的最大次幂和3的最大次幂）。如果做0次，就只需要找到最小值即可。现在只剩下做一次lcm的情况了。对于这种情况，我们暴力搜索一边所有可能解即可。在比较大小的时候，我们可以通过对于2^a3^b求log2，得到的是a + log2(3)b，只需要比较这个值的大小即可。（可能会有精度误差，不过还是可以通过本题）
代码如下：
#include <bits/stdc++.h> using namespace std; const int maxn = 50000 + 10; const int maxm = 1000 + 10; int a[maxn],b[maxn]; int ans[maxn][5]; int n; int main() { scanf("%d",&n); for(int i = 1;i <= n;i++) scanf("%d%d",&a[i],&b[i]); if(n == 1) {printf("%d %d %d %d\n",a[1],b[1],a[1],b[1]);return 0;} int mina = maxm,minb = maxm; int minap = 0,minbp = 0; int maxa = 0,maxb = 0; int maxap = 0,maxbp = 0; for(int i = 1;i <= n;i++){ if(a[i] < mina) {mina = a[i];minap = i;} if(a[i] > maxa) {maxa = a[i];maxap = i;} if(b[i] < minb) {minb = b[i];minbp = i;} if(b[i] > maxb) {maxb = b[i];maxbp = i;} } if(n == 2){ printf("%d %d %d %d\n",maxa,maxb,maxa,maxb); printf("%d %d %d %d\n",mina,minb,mina,minb); return 0; } ans[1][1] = maxa;ans[1][2] = maxb; ans[1][3] = maxa;ans[1][4] = maxb; int p1 = 2,p2 = n - 1; if(n != 3) {ans[p1][1] = maxa;ans[p1][2] = maxb;} //1 * gcd int nowa = maxm,nowb = maxm; for(int i = 1;i <= n;i++){ //1 * gcd if(i != maxap && i != maxbp){ int tmp1 = min(maxa,a[i]),tmp2 = min(maxb,b[i]); if(nowa + nowb * log2(3) > tmp1 + tmp2 * log2(3)){ nowa = tmp1;nowb = tmp2; } } else { int mmaxa = 0,mmaxb = 0; for(int j = 1;j <= n;j++){ if(j == i) continue; mmaxa = max(mmaxa,a[i]); mmaxb = max(mmaxb,b[i]); } int tmp1 = min(mmaxa,a[i]),tmp2 = min(mmaxb,b[i]); if(nowa + nowb * log2(3) > tmp1 + tmp2 * log2(3)){ nowa = tmp1;nowb = tmp2; } } } ans[p1][3] = nowa;ans[p1][4] = nowb; // if(n != 3) {ans[p2][3] = mina;ans[p2][4] = minb;} //1 * lcm nowa = 0;nowb = 0; for(int i = 1;i <= n;i++){ //1 * lcm if(i != minap && i != minbp){ int tmp1 = max(mina,a[i]),tmp2 = max(minb,b[i]); if(nowa + nowb * log2(3) < tmp1 + tmp2 * log2(3)){ nowa = tmp1;nowb = tmp2; } } else { int mmmina = maxm,mmminb = maxm; for(int j = 1;j <= n;j++){ if(j == i) continue; mmmina = min(mmmina,a[i]); mmminb = min(mmminb,b[i]); } int tmp1 = max(mmmina,a[i]),tmp2 = max(mmminb,b[i]); if(nowa + nowb * log2(3) < tmp1 + tmp2 * log2(3)){ nowa = tmp1;nowb = tmp2; } } } ans[p2][1] = nowa;ans[p2][2] = nowb; // for(int i = p1 + 1;i <= p2 - 1;i++){ ans[i][1] = maxa;ans[i][2] = maxb; ans[i][3] = mina;ans[i][4] = minb; } ans[n][1] = mina;ans[n][2] = minb; ans[n][3] = mina;ans[n][4] = minb; for(int i = 1;i <= n;i++){ printf("%d %d %d %d\n",ans[i][1],ans[i][2],ans[i][3],ans[i][4]); } return 0; }