例如 N = 18 L = 2：
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
都是满足要求的，但是我们输出更短的 5 6 7
数据范围： 
， 
[编程题]序列和
- 热度指数：104043 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
给出一个正整数 N 和长度 L ，找出一段长度大于等于 L 的连续非负整数，他们的和恰好为 N 。答案可能有多个，我我们需要找出长度最小的那个。
例如 N = 18 L = 2：
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
例如 N = 18 L = 2：
5 + 6 + 7 = 18
3 + 4 + 5 + 6 = 18
输入描述:
输入数据包括一行： 两个正整数N(1 ≤ N ≤ 1000000000),L(2 ≤ L ≤ 100)
输出描述:
从小到大输出这段连续非负整数，以空格分隔，行末无空格。如果没有这样的序列或者找出的序列长度大于100，则输出No
示例1
输入
18 2
输出
5 6 7
示例2
输入
30 13
输出
No
说明
无法由非负整数构成
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scan=new Scanner(System.in);
int N=scan.nextInt();
int L=scan.nextInt();
int first;
int last;
for(;L<=100;L++){
first=((2*N/L)-L+1)/2;
last=first+L-1;
if(((first+last)*L)/2==N){
for(int i=0;i<L-1;i++){
System.out.print(first+" ");
first++;
}
System.out.print(last);
return;
}
}
System.out.print("No");
return;
}
} java版本
发表于 2020-07-31 14:28:28
回复(0)
运用等差数列的方法得到最小长度数列的第一位数a1,因为可能得到的是float，所以通过将得到的数列取相整数加判断是否等于N，判断成功就可把整数数组的数字显示，注意最后个数字没有空格，需要if两种情况。
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int N= input.nextInt();
int L= input.nextInt();
int b;
int a;
int flag=0;
for(int i=L;i<101;i++){
a= N/i-(i-1)/2;
b=i*a;
for(int k=0;k<i;k++){
b=b+k;}
if(b==N){
for(int j=0;j<i;j++){
if(j<i-1){
int c=a+j;
flag=1;
System.out.print(c+" ");
}
else if(j==i-1){
int c=a+j;
flag=1;
System.out.print(c);
}
}
break;
}
if(i==100 && flag==0){
System.out.print("No");
}
}
}
}
发表于 2020-05-15 13:00:14
回复(0)
Java版本
根据本题思路，假设有L个数组成N，那么即有L*a1+((L-1）*L)/2)*d=N,因为该题求的是连续函数，所以d为1，那么即可以根据L和N求出a1，且a1必须为整数，且L不大于100。那么可得a1 = (2N - (L-1)L) / (2 * L)，切记最后输出的行末不能带有空格。
根据本题思路，假设有L个数组成N，那么即有L*a1+((L-1）*L)/2)*d=N,因为该题求的是连续函数，所以d为1，那么即可以根据L和N求出a1，且a1必须为整数，且L不大于100。那么可得a1 = (2N - (L-1)L) / (2 * L)，切记最后输出的行末不能带有空格。
import java.util.Scanner;
public class Main {
public static void main(String[] args){
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int L = input.nextInt();
show(N,L);
}
public static int show(int N,int L){
int i = L;
while(i <= 100){
int a = (2*N - i*(i-1))/(2*i);
if((2*N - i*(i-1))%(2*i) == 0 && a >= 0){
for(int j = 0;j < i-1;j++){
System.out.print(a + " ");
a = a + 1;
}
System.out.print(a);
return 0;
}
i = i + 1;
}
if(i > 100){
System.out.print("No");
return 0;
}
return 0;
}
}
编辑于 2020-04-27 17:53:30
回复(1)
package mypack_5;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Demo2 {
public static void main(String[] args) {
//就是不喜欢把函数直接写在主方法里面...^^^...
function();
}
public static void function() {
Scanner scan = new Scanner(System.in);
while (scan.hasNext()) {
int N = scan.nextInt();
int L = scan.nextInt();
boolean flag = false;
for (int i = L; i <= 100; i++) {
if ((2 * N + i - i * i)>=0 &&(2 * N + i - i * i) % (2 * i) == 0) {
flag = true;
int first = (2 * N + i - i * i) / (2 * i);
for (int j = 0; j < i - 1; j++) {
int next = first + j;
System.out.print(next + " ");
}
System.out.print(first + i - 1);
break;
}
}
if (flag == false)
System.out.println("No");
}
}
}
也是使用了等差数列公式，但是对前面的代码进行了一点小小的改进。让代码更加健壮。
改进之处就是在第一个if判断里面加入了(2 * N + i - i * i)>=0 这个条件。
如果不加这个条件，如果你自己在本地测试的时候输入N=2 ， L=2 ，那么结果会输出-1 0 1 2
不知道为啥如果不加上这个判断条件，线上的用例都也可以通过...
发表于 2020-04-13 15:21:44
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = 0;
int L = 0;
if (scanner.hasNextInt()) {
N = scanner.nextInt();
}
if (scanner.hasNextInt()) {
L = scanner.nextInt();
}
int a = 0;
double t = 0;
for (int i = L; i <= 100; i++) {
t = N / (i * 1.0) - (i * 1.0 - 1) / 2;
a = (int) t;
if ((double) a == t) {
for (int j = 0; j < i; j++, a++) {
System.out.print(a);
if (j < i - 1) {
System.out.print(" ");
}
}
break;
}
if (a < 0 || i == 100) {
System.out.println("No");
break;
}
}
}
}
发表于 2020-03-29 15:38:53
回复(0)
运行时间：65ms
占用内存：10560k
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int l=scanner.nextInt();
boolean findResult=false;
if(n>=l-1){
for(int i=l;i<=Math.min(100,n+1);i++){
if(i%2==1 && n%i==0){
System.out.print(n/i-i/2);
for(int j=1;j<i;j++){
int temp=n/i-i/2+j;
System.out.print(" "+temp);
}
findResult=true;
break;
}else if(i%2==0 && n%i!=0 && (n*2)%i==0){
System.out.print(n/i-i/2+1);
for(int j=1;j<i;j++){
int temp=n/i-i/2+1+j;
System.out.print(" "+temp);
}
findResult=true;
break;
}
}
}
if(!findResult){
System.out.print("No");
}
}
}
I为奇数和偶数时分别各只有一种情况符合条件。
为减少循环次数排除掉了除了N=1，I=2以外所有N小于I的情况。
话说这个还得额外写个Scanner，我以为只要写算法逻辑来着
编辑于 2020-03-26 17:19:28
回复(0)
看过来，看过来!
由倒序相加法知
2Sn=(a1+an)*n
所以我们尝试分解2Sn=x*y
并建立以下方程：
a1+an=x，n=y
由于公差d=1，an-a1=n-1
于是得到以下方程组
an+a1=x
an-a1=n-1=y-1
解之得
a1=(x-y+1)/2
an=(x+y-1)/2
显然只要a1有正整数解an就有正整数解
因此下面我们枚举y
public class Main{
public static void main(String args[]){
java.util.Scanner scan=new java.util.Scanner(System.in);
int N=2*scan.nextInt(),L=scan.nextInt();
for(int y=L;y<=100;y++)if(N%y==0){
int x=N/y;
if((x-y+1)%2==0){
int a1=(x-y+1)/2,an=a1+y-1;
if(a1>=0){
System.out.print(a1);
for(int i=a1+1;i<=an;i++)System.out.print(" "+i);
return;
}
}
}
System.out.println("No");
}
}
public static void main(String args[]){
java.util.Scanner scan=new java.util.Scanner(System.in);
int N=2*scan.nextInt(),L=scan.nextInt();
for(int y=L;y<=100;y++)if(N%y==0){
int x=N/y;
if((x-y+1)%2==0){
int a1=(x-y+1)/2,an=a1+y-1;
if(a1>=0){
System.out.print(a1);
for(int i=a1+1;i<=an;i++)System.out.print(" "+i);
return;
}
}
}
System.out.println("No");
}
}
发表于 2020-03-20 17:45:21
回复(0)
分享我的41ms的Java代码，请大家帮助我优化：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] nl = sc.nextLine().split(" ");
int n = Integer.parseInt(nl[0]);
int l = Integer.parseInt(nl[1]);
int num = 0;
for(int i = 1; i < l; ++i) num += i;
int base = -1;
while(l < 101){
if(num <= n && (n - num) % l == 0){
base = (n - num) / l;
break;
}
num += l++;
}
if(base == -1) System.out.println("No");
else{
System.out.print(base);
for(int i = 1; i < l; ++i){
System.out.print(' ');
System.out.print(base + i);
}
System.out.println();
}
sc.close();
}
}
编辑于 2020-03-20 08:44:37
回复(7)
一、解题思路
假设数N等于长度为i的连续整数之和，
1）若i为奇数，则必定有N%i==0，且该序列存在一个中心元素mid=N/i，该序列关于中心元素mid对称
2）若i为偶数，则必定有N*1.0/i - N/i == 0.5，即序列的中位数到左右两个整数的距离都是0.5
遍历序列长度L<=i<=100，若以上两种情况都不满足，说明没有解，输出No
二、AC代码
import java.util.*;
public class Test{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
printSeq(N,L);
}
public static void printSeq(int N, int L){
for(int i=L;i<=100;++i){
//odd sequence has the mid element
if(i%2==1){
if(N%i==0){
int mid = N/i;
System.out.print(mid-i/2);
for(int j=mid-i/2+1;j<=mid+i/2;++j)
System.out.print(" "+j);
return;
}
}
//even sequence has the median
else{
if(N%i!=0){
if(N*1.0/i-N/i == 0.5){
System.out.print(N/i-i/2+1);
for(int j=N/i-i/2+2;j<=N/i+i/2;++j)
System.out.print(" "+j);
return;
}
}
}
}
System.out.print("No");
return;
}
}
public class Test{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
printSeq(N,L);
}
public static void printSeq(int N, int L){
for(int i=L;i<=100;++i){
//odd sequence has the mid element
if(i%2==1){
if(N%i==0){
int mid = N/i;
System.out.print(mid-i/2);
for(int j=mid-i/2+1;j<=mid+i/2;++j)
System.out.print(" "+j);
return;
}
}
//even sequence has the median
else{
if(N%i!=0){
if(N*1.0/i-N/i == 0.5){
System.out.print(N/i-i/2+1);
for(int j=N/i-i/2+2;j<=N/i+i/2;++j)
System.out.print(" "+j);
return;
}
}
}
}
System.out.print("No");
return;
}
}
编辑于 2020-03-18 23:17:53
回复(0)
import java.util.Scanner;
public class XulieSum {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();
int l=s.nextInt();
for(int i=l;i<=100;i++) {
if((n*2)%i==0)//判断首项加末项除以项数是否为整数
{
int m=(n*2/i)-(i-1);//两个首项的和
int k=m/2;//首项
if(m%2==0) {
for(int j=0;j<i-1;j++) {
System.out.print(k+++" ");
}
System.out.println(k);
return ;
}else {
continue;
}
}else{
continue;
}
}
System.out.println("No");
}
}
发表于 2018-01-16 20:54:11
回复(0)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
for (int i = L; i <= 100; i ++) {
if ((2 * N + i - i * i) % (2 * i) == 0) {
int a1 = (2 * N + i - i * i) / (2 * i);
for (int j = 0; j < i-1; j ++) {
System.out.print(a1 + j + " ");
}
System.out.println(a1 + i - 1);
return;
}
}
System.out.println("No");
}
}
发表于 2017-03-12 21:24:44
回复(1)
- 这道题和等差数列求和公式有关
- 2N = len(2ai + len - 1),所以只要遍历L<= len <= sqrt(2N) + 1，且len<=100之间的长度，满足len为2N的因数，且另一个因数为2N/len，这个时候就可以求出ai来了。只要(2N/len+1-len)%2==0，且商大于等于0，那么这个数就存在
-
可以知道，我的算法只需要在线性时间复杂度内就可以有效解出（给自己赞一个） ``` public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub Scanner in = new Scanner(System.in); int N = in.nextInt(); int L = in.nextInt(); int charge = 0; boolean flag = false;
// ?List<Integer> temp = new ArrayList<Integer>();
//get the mod of N
int len = L;
for(; len <= Math.sqrt(2*N)+1 && len <= 100; ++len){
if(N*2 % len == 0){
charge = 2*N/len;
charge = charge + 1 - len;
if(charge >= 0 && charge % 2 == 0){
charge /= 2;
flag = true;
break;
}
}
}
int sum = 0;
if(flag){
for(int j = 0; j < len-1; ++j){
sum += charge+j;
System.out.print(charge+j + " ");
}
System.out.println(charge+len-1);
}else{
System.out.println("No");
}
in.close();
}
} ```
发表于 2017-03-08 21:42:39
回复(0)
import java.util.Scanner;
/*
* 题目需要找出一段长度大于等于L的连续非负整数，使得其和等于N。L要尽可能小。
* 考虑是连续非负整数，所以其和我们能用中位数来表示，分两种情况：
* 情况一，长度为奇数的情况：
* 此时中位数一定是整数，N = 中位数 x L
* 情况二，长度为偶数的情况：
* 此时中位数肯定是xx.5的形式，N = xx.5 * L
* 所以我们从长度L开始枚举，至100为止，分奇偶讨论。
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt(), l = in.nextInt();
in.close();
int bg = -1, ed = -1;
for (int i = l; i <= 100; ++i) {
// 奇数，中位数一定是整数
if (i % 2 == 1 && n % i == 0) {
int mid = n / i;
bg = mid - (i - 1) / 2;
ed = mid + (i - 1) / 2;
if (bg >= 0) // 答案要合法，即需要是非负整数
break;
}
// 偶数，中位数一定是0.5形式
if (i % 2 == 0 && (double)n / i - n / i == 0.5f) {
int mid = n / i;
bg = mid - i / 2 + 1;
ed = mid + i / 2;
if (bg >= 0)
break;
}
}
if (bg >= 0) {
for (int i = bg; i < ed; ++i) {
System.out.print(i + " ");
}
System.out.println(ed);
}
else {
System.out.println("No");
}
}
}
发表于 2017-03-08 16:26:25
回复(2)
import java.util.Scanner;
public class Main3 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
int x = 0;
double i = L;
int j = 0;
for (; i <= 100; i++) {
if ((N - i * (i - 1) / 2) % i == 0) { //因为除二所以应该是double
x = (int) ((N - i * (i - 1) / 2) / i);
if (x >= 0) break;
}
}
if (i >= 101)
System.out.println("No");
else {
for (; j < i - 1; j++)
System.out.print(x + j + " ");
System.out.print( x+(int)i-1);
}
}
}
编辑于 2017-03-08 13:55:44
回复(0)
//想知道我的代码没有考虑哪种情况 通过率90%
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int L = sc.nextInt();
int x = 0;
int i = L;
int j = 0;
for(; i <= 100; i++){
if((N - i*(i-1)/2) % i == 0)
x = (N - i*(i-1)/2) / i;
if(x != 0) break;
}
if(i > 100)
System.out.println("No");
else{
for(; j < i - 1; j++)
System.out.print(x+j + " ");
System.out.print(敏感词re>
}
编辑于 2017-03-08 10:43:44
回复(3)
问题信息
通过挑战的用户
-
2023-03-11 14:27:09 -
2022-09-16 16:30:44
-
2022-09-16 16:18:14 -
2022-09-16 15:28:34 -
2022-09-16 12:01:29
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
