题目简介
-
给定一个正整数 \(n\),构造一个数列 \(p\),使 \(1\) 到 \(n\) 中每一个数都出现且只出现 \(1\) 次。
-
求最大的 \(\sum\limits_{i=1}^n\operatorname{lcm}(i, p_i)\),并输出取得最大值时的数列。
思路
基础知识:\(\operatorname{lcm}(a,b)=\dfrac{a\times b}{\operatorname{gcd}(a,b)}\)。
\(\operatorname{gcd}(a,a+1)=1\)。
根据上面两个知识,我们可以得到相邻两项的 LCM 即为他们的乘积,根据贪心的思想,我们从后往前遍历,将相邻两项的位置互换,这样每次都会使相对较大的两个数相乘,使最终的结果最大,其中如果 \(n\) 是奇数,\(1\) 的位置不变即可。
代码
#include <bits/stdc++.h>
using namespace std;
int t,n;
int main() {
scanf("%d",&t);
while(t--){
scanf("%d",&n);
if(n&1){
putchar('1');
putchar(' ');
for(int i=2;i<=n;i+=2){
printf("%d %d ",i+1,i);
}
putchar('\n');
}
else{
for(int i=1;i<=n;i+=2){
printf("%d %d ",i+1,i);
}
putchar('\n');
}
}
return 0;
}
标签:putchar,int,题解,scanf,CF1712B,Woeful,operatorname
From: https://www.cnblogs.com/Dregen-Yor/p/16589026.html