[编程题] 翻转数列
小Q定义了一种数列称为翻转数列:
给定整数n和m, 满足n能被2m整除。对于一串连续递增整数数列1, 2, 3, 4…, 每隔m个符号翻转一次, 最初符号为’-‘;。
例如n = 8, m = 2, 数列就是: -1, -2, +3, +4, -5, -6, +7, +8.
而n = 4, m = 1, 数列就是: -1, +2, -3, + 4.
小Q现在希望你能帮他算算前n项和为多少。
时间限制：1秒
空间限制：32768K
题目来源：腾讯2018春招技术类编程题汇总—牛客网
输入描述：
输入包括两个整数n和m(2 <= n <= 10^{9}, 1 <= m), 并且满足n能被2m整除
输出描述：
输出一个整数，表示前n项和。
输入样例：
8 2
输出样例：
8
解题过程
最开始写代码时，没有注意到输入范围使用了int导致出错，然后更改为如下代码：
public class Main { //直接法(最慢)
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n, m, sum = 0;
ArrayList<Long> array = new ArrayList<Long>();
n = sc.nextLong();
m = sc.nextLong();
if (n >= 2 && n % (2 * m) == 0) {
long i = 0, k = 1;
boolean flag = true;
while (i < n) {
if (i % m == 0) {
flag = !flag;
}
if (flag) {
array.add(new Long(k));
sum += k;
} else {
array.add(new Long(0 - k));
sum -= k;
}
i++;
k++;
}
System.out.println(sum);
} else {
System.out.println("输入有误");
}
}
}
但是，当输入数值较大的时候此方法运行时间不能满足题目要求，且可能会导致内存溢出,如下图：
因此对题目再次仔细观察后发现数列前后相加刚好是从n-1开始，公差为2的等差数列（忽略符号），所以将代码修改如下：
public class Main{ //优化后解法
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
long n,m,sum=0;
n=sc.nextLong();
m=sc.nextLong();
if (n >= 2 && n % (2 * m) == 0) {
boolean flag=false;
for(long i=0,k=n-1;i<n/2;i++){
if (i % m == 0) {
flag = !flag;
}
if (flag) {
sum += k;
} else {
sum -= k;
}
k-=2;
}
System.out.println(sum);
}else{
System.out.println("输入有误");
}
}
}
再次提交运行，发现还是超时，然后通过百度搜索相关博客后找到了最简洁高效的代码：
public class Main{ //最优解
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
long n,m,sum=0;
n=sc.nextLong();
m=sc.nextLong();
if (n >= 2 && n % (2 * m) == 0) {
sum=n*m/2;
System.out.println(sum);
}else{
System.out.println("输入有误");
}
}
}
试题分析
题目中有提到，n能被2m整除，因此尝试将数列划分为长度为2m的一小段来进行找规律。
比如题目中的输入为
8 2
数列为
-1 -2 3 4 -5 -6 7 8
第一个长度为2m(m=2)的数列为
-1 -2 3 4
观察到-1+3=-2+4，即m+1项减去第1项等于m，又因为长度是2m，所以共有m个这样的组合，即和为m*m，第二个长度为2m的数列同样如此，因此长度为n时其和为n/2*m
最后要注意从键盘获取long型数值要使用nextLong()