首页 > 试题广场 >

完美的序列

[编程题]完美的序列
  • 热度指数:2634 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
小易定义一个数字序列是完美的,当且仅当对于任意,都满足,即每个数字都要大于等于前面所有数字的和。
现在给定数字序列,小易想请你从中找出最长的一段连续子序列,满足它是完美的。

输入描述:
第一行数据组数。对于每组数据,第一行一个整数,接下来一行个整数表示序列。



输出描述:
对于每组数据,一行一个数字表示最长完美的连续子序列的长度。
示例1

输入

2
5
1 3 9 2 6
5
4 2 9 16 7

输出

3
3
import sys

def find_longest(l):
    i, j = 0, 1
    cur = 0
    while j < len(l) and i < len(l):
        while j < len(l) and sum(l[i:j]) <= l[j]:
            j += 1
        cur = max(cur, j - i)

        i = j
        j = i + 1
        
    return cur
    

n = int(sys.stdin.readline())
for i in range(n):
    size = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))
    print(find_longest(a))

发表于 2020-03-30 06:28:38 回复(4)
采用双指针滑动窗口来求解
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while(T-- > 0){
            int n = sc.nextInt();
            int[] nums = new int[n];
            for(int i = 0; i < n; i++) nums[i] = sc.nextInt();
            System.out.println(solve(nums));
        }
    }
    
    // 直接用滑动窗口计算窗口内的元素之和来判断
    private static int solve(int[] nums) {
        int left = 0, right = 1;
        long sum = nums[0];
        int maxLen = 0;
        while(right < nums.length){
            if(nums[right] >= sum){
                maxLen = Math.max(maxLen, right - left + 1);
                sum += nums[right];
                right ++;
            }else{
                sum -= nums[left];
                left ++;
            }
        }
        return maxLen;
    }
}


发表于 2020-10-22 15:52:04 回复(0)
双指针滑动窗口 AC
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();
    while(m-- > 0) {
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(longestSub(nums));
    }
}

public static int longestSub(int[] nums) {
    int i = 0, j = 1, max = 0, sum = nums[0],n = nums.length;
    while(j < n) {
        if(nums[j] >= sum) {
            sum += nums[j];
            max = Math.max(max, j-i+1);
            j++;
        } else {
            sum -= nums[i];
            i++;
        }
    }
    return max;
}


编辑于 2020-08-07 14:52:51 回复(1)
 import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        for (int i = 0; i < t; i++) {
            int j = scanner.nextInt();
            int[] arr = new int[j];
            for (int i1 = 0; i1 < j; i1++) {
                arr[i1] = scanner.nextInt();
            }
            System.out.println(demo4(arr));
        }


    }
    //2 3 5 9 18
    public static int demo4(int[] arr) {
        //两个辅助指针,标记从哪里开始
        int left = 0;
        int right = 1;
        //最大子序列长度
        int maxCount = 1;
        //当前子序列长度
        int curCount = 1;
        int sum = arr[0];
        //当右边指针未达到数组最右边边界时
        while (right < arr.length) {
            //如果满足条件
            if (arr[right] >= sum) {
                //将当前值加入总和
                sum += arr[right];
                //当前子序列的长度
                curCount = right - left + 1;
                //right指针向后移动一位
                right++;
                //更新最大长度
                maxCount = maxCount > curCount ? maxCount : curCount;
            } else {
                //如果不满足条件,则需要从sum中减去left所在位置的值
                sum -= arr[left];
                //将left向后移动一位
                left++;
            }
        }
        return maxCount;
    }


}

编辑于 2020-04-06 18:02:39 回复(4)
设置起点start,遍历数组,遍历过程中不断更新start和最大长度
#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> n;
    while(n--) {
        cin >> m;
        int nums[m];
        int start = 1;
        int res = 0;
        for(int i = 0; i < m; i++) {
            cin >> nums[i];
        }
        int sum = nums[0];
        for(int i = 1; i < m; i++) {
            if(sum <= nums[i]) {
                sum += nums[i];
                res = max(res, i - start + 1);
            }else {
                start = i;
                sum = nums[i];
            }
        }
        cout << res << endl;
    }
}

发表于 2020-04-01 07:51:54 回复(7)
C++双指针
#include<vector>
#include<iostream>
using namespace std;

vector<int> solution(vector<vector<int> >&input){
    vector<int> res;
    for(int i = 0; i < input.size(); i++){
        int left = 0;
        int sum = 0;
        int len = 0;
        for(int j = 0; j < input[i].size()-1; j++){
            sum += input[i][j];
            if(sum > input[i][j+1]){
                len = max(len, j- left+1);
                left = j+1;
                sum = 0;   
            }
        }
        if(len == 0) len = input[i].size();
        res.push_back(len);
    }
    return res;
}

int main(){
    int a;
    cin >> a;
    vector<vector<int> > input;
    for(int i = 0; i < a; i++){
        int b;
        cin >> b;
        vector<int> temp;
        int number;
        for(int i = 0; i < b; i++){
            cin >> number;
            temp.push_back(number);
        }
        input.push_back(temp);
    }
    vector<int> res = solution(input);
    for(auto cha : res) cout << cha << endl;
    return 0;
}


编辑于 2020-05-11 12:58:51 回复(0)
T = int(input())
list1 = []
for i in range(T):
    n = int(input())
    list1.append(list(map(int,input().split())))

for i in range(T):
    sum = 0
    num = 0
    num_list = []
    for value in list1[i]:
        if sum <=  value :
            sum = sum + value
            num = num + 1
            num_list.append(num)
        else:
            num = 1
            sum = value
    print(max(num_list))

#提示出错的案例单独运行就是正确答案,生气



发表于 2020-03-06 22:12:18 回复(1)
一开始考虑的是动态规划,设 dp[i, j] 为 序列 i~j 中最长完美子序列长度,然后在找关系时发现不好找,如果把 dp[i, j] 设为 序列 i~j 的元素合。那么关系就好找了:
dp[i, j] = dp[i, j - 1] + ar[j]  如果 ar[j] >= dp[i, j - 1] 此时可以更新长度
如果 ar[j]  < dp[i, j - 1] 那么此时 j 就不需要往后移动了,我们移动 i
让 i 从 0 到 n 移动,i 移动完后,我们就找出了所有 完美子序列的长度
初始值就时 i == j 时,元素本身就为 完美子序列,dp[i, j] = ar[i]
然后 1Ai10^9 那么 dp[i, j] 就可能出现 int 过界,因此用 long 矩阵
编码完后,发现内存超了。
再看一遍自己的编码,发现其实并不能算是 动态规划。 dp 中大部分元素我是不需要的,我只需要维护一个 当前 i~j 的元素和即可。
C#代码:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

public class Program
{
    public static void Main(string[] args)
    {
        int T = int.Parse(Console.ReadLine());

        for(int k = 0; k < T; ++k)
        {
            int n = int.Parse(Console.ReadLine());
            string[] ipts = Console.ReadLine().Split(' ');
            int[] ar = new int[n];

            for (int i = 0; i < n; ++i) ar[i] = int.Parse(ipts[i]);

            long sum = 0;
            int len = 1;
            int tempLen = 1;
            for(int i = 0; i < n; ++i)
            {
                sum = ar[i];
                tempLen = 1;
                for(int j = i + 1; j < n; ++j)
                {
                    if (ar[j] >= sum)
                    {
                        ++tempLen;
                        sum += ar[j];
                    }
                    else break;
                }
                len = Math.Max(len, tempLen);
            }
            Console.WriteLine(len);
        }
    }

}


发表于 2020-09-29 19:36:34 回复(0)
#include<stdio.h>
#include<stdlib.h>

void sort(int *a, int l)//a为数组地址,l为数组长度。
{
    int i, j;
    int v;
    //排序主体
    for(i = 0; i < l - 1; i ++)
        for(j = i+1; j < l; j ++)
        {
            if(a[i] > a[j])//如前面的比后面的大,则交换。
            {
                v = a[i];
                a[i] = a[j];
                a[j] = v;
            }
        }
}

int main()
{
    int T, n, m;
    int XL[100000];
    int XB[100000] = {0};
    int pm = 1; // 序列长度
    int sum = 0;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        for(int i = 0; i < n; i++)
        {
            scanf("%d", &XL[i]);
        }
        sort(XL, n); // 2 4 7 9 16
        for(int i = 1; i <= n; i++)
        {
            for(int j = 0; j < i; j++)
            {
                if(XB[j] != 1)
                {
                    sum += XL[j];
                }

            }

            if(sum < XL[i])
            {
                pm += 1;
            }
            else
            {
                XB[i+1] = 1;
            }

            sum = 0;
        }
        printf("%d\n", pm);
        pm = 0;
    }
    return 0;
}测试对的,但是提交一个也没有对
发表于 2023-07-04 14:12:21 回复(0)

照着官方Java答案写的C++版本,代码能知道在干嘛,但是我暂时不知道为什么用双指针滑动窗口是对的
希望有知道的牛友解答一下

 int prefectSequence(vector<int>& input) {
     int left = 0, right = 1;
     long sum = input[0];
     int maxLen = 0;

     while (right < input.size()) {
         if (input[right] >= sum) {
             maxLen = max(maxLen, right - left + 1);
             sum += input[right];
             right++;
         }
         else {
             // 这里就是我搞不懂的地方了
             // 我不理解为什么这里双指针滑动窗口的正确的
             sum -= input[left];
             left++;
         }
     }
     return maxLen;
 }

 int main() {
     int T,n,num;
     cin >> T;
     vector<int> input;
     while (T-- >0)
     {
         cin >> n;
         for (int i = 0; i < n; i++) {
             cin >> num;
             input.push_back(num);
         }
         cout<<prefectSequence(input) << endl;
         input.clear();
     }
     return 0;
 }
发表于 2022-09-03 00:05:15 回复(0)
#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MAXN = 1e5 + 50;
int a[MAXN];


int main() {
    int T, n;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        LL curr = a[0];
        int ans = 0;
        for (int l = 0, r = 1; r < n; ++r) {
            while (curr > a[r]) {
                curr -= a[l++];
            }
            ans = max(ans, r - l + 1);
            curr += a[r];
        }
        cout << ans << endl;
    }
    return 0;
}

发表于 2022-04-27 15:11:06 回复(0)
a=int(input())
ar1=[]
ar8=[]
j=0
while(j<a):
    b=int(input())
    ar1.append(list(map(int, input().split(' '))))
    j=j+1
for i in range(len(ar1)):
    fun1(ar1[i])
    print(max(ar8))
    ar8=[]
def fun1(arr):
    for i in range(len(arr)):
        if(i==len(arr)-1):
            num=1
            ar8.append(num)
            break
        num=1
        ad=arr[i]
        fun2(i+1,arr,num,ad)
def fun2(kep,arr,num,ad):
    global ar8
    for i in range(kep,len(arr)):
        if(arr[i]>=ad):
            num=num+1
            ad=ad+arr[i]
            if(i==len(arr)-1):
                ar8.append(num)
                break
            kep=kep+1
            fun2(kep,arr,num,ad)
        if(i==len(arr)-1):
            ar8.append(num)
            break
发表于 2022-04-02 23:23:32 回复(0)
仿照评论区未央大神的写了个python版
T = int(input())
while T:
    T -= 1
    n = int(input())
    nums = list(map(int,input().split()))
    i = 0
    j = 1
    res = 0
    sum = nums[0]
    while j < n: 
        if nums[j] >= sum:
            sum += nums[j]
            res = max(res, j-i+1)
            j+=1
        else:
            sum -= nums[i]
            i+=1
    print(res)

发表于 2020-08-08 11:53:15 回复(0)
Java,双指针加滑动窗口
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while(t--!=0){
            int n = sc.nextInt();
            int[] nums = new int[n];
            for(int i = 0 ; i < n ; i ++ ) nums[i] = sc.nextInt();
            int l = 0 ;
            int len = 0 ;
            int sum = 0 ;
            for(int i = 0 ; i < n ;){
                if( sum <= nums[i]){
                    sum += nums[i];
                    i++;
                }
                else{
                    len = Math.max(len,i - l );
                    sum -= nums[l];
                    l++;
                    if(l > i) i++;
                }
            }
            len = len == 0 ? n : len ;
            System.out.println(len);
        }
 
    }
}

发表于 2020-08-08 01:20:32 回复(0)
from functools  import reduce

n=int(input())
for niter in range(n):
    nlong = int(input())
    a = list(map(int,input().split()))
    
    judge=[]
    for i in range(0,len(a)+1):
        k=i+1
        l=1
        while True:
            if k<len(a) and a[k]>=reduce(lambda x,y:x+y,a[i:k]):
                k = k+1
                l=l+1
            else:
                break
        judge.append(l)
    print(max(judge)) 

发表于 2020-08-07 18:31:50 回复(0)
t = int(input())
for _ in range(t):
    n = int(input())
    li = list(map(int, input().split(" ")))
    result = left = 0
    left_sum = 0
    for i in range(1, len(li)):
        left_sum += li[i - 1]
        while li[i] < left_sum and left < i:
            left_sum -= li[left]
            left += 1
        result = max(result, i - left + 1)
    print(result)

发表于 2020-07-28 23:16:10 回复(0)
双指针
#include<iostream>
using namespace std;
const int maxn = 100005;
int arr[maxn];
int main()
{
    int T, n, sum, ans, left, right;
    scanf("%d", &T);
    while(T--)
    {
        left = right = sum = ans = 0;
        scanf("%d", &n);
        for(int i = 0; i < n; ++i) scanf("%d", &arr[i]);
        while(right < n)
        {
            while(right < n && sum <= arr[right])
                sum += arr[right++];
            ans = max(ans, right - left);
            if(right >= n) break;
            while(sum > arr[right])
                sum -= arr[left++];
        }
        printf("%d\n", ans);
    }
}


发表于 2020-04-07 14:09:54 回复(0)
data = []
length = int(input()) * 2
x = 0
while x < length:
    s = input()
    if s != "":
        temp = [int(i) for i in s.split()]
        data.append(temp)
        x += 1
    else:
        break

i = 0

while i < length:
    n = data[i ][0]
    lst = data[i  + 1]
    j = 1
    s = lst[0] 
    while j <= n:
        if s > lst[j]:
            break
        else:
            s += lst[j]
            j += 1
    print (j)
    i += 2

发表于 2020-04-07 09:50:43 回复(0)
def countf(a,b,count):
    if a<=b:
        count=count+1
        return count
    else :
        count=1
        return count 
        
n=int(input())
for i in range(n):
    m=int(input())
    data=list(map(int,input().split(' ')))
    count_max=1
    count_one=1
    for j in range(m-1):
        count_one=countf(data[j],data[j+1],count_one)
        if count_one>count_max:
            count_max=count_one
    print(count_max)

只有70%😂
发表于 2020-04-06 17:26:50 回复(0)
#include <iostream>
(720)#include <vector>
 
using namespace std;
int main()
{
    int t;
    cin >>t;
    vector<vector<int>> arr(t);
    for (int i = 0;i < t;i++)
    {
        int len;
        cin >> len;
        for (int j= 0;j < len;j++)
        {
            int a;
            cin >> a;
            arr[i].push_back(a);
        }
    }
 
    vector<int> maxlen(t,0);
    for (int i = 0;i < t;i++)
    {
 
        int left=0,sum = 0,len = 0;
        while (left <arr[i].size())
        {
 
            for (int j = left;j < arr[i].size();j++)
            {
                if (arr[i][j] >= sum)
                {
                    sum += arr[i][j];
                    len++;
                    maxlen[i] = len > maxlen[i] ? len : maxlen[i];
                }
                else
                {
                    sum = 0;
                    len = 0;
                    break;
                }
            }
            left++;
        }
 
    }
 
    for (int i = 0;i < maxlen.size(); ++i)
    {
        cout << maxlen[i]<< " ";
        cout << endl;
    }
 
    return 0;
}

发表于 2020-03-15 00:49:55 回复(0)