首页 > 专题系列 > Java解POJ > POJ 3061 Subsequence [解题报告] Java
2013
11-12

POJ 3061 Subsequence [解题报告] Java

Subsequence

问题描述 :

A sequence of N positive integers (10 < N < 100 000), each of them less than or equal 10000, and a positive integer S (S < 100 000 000) are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to S.

输入:

The first line is the number of test cases. For each test case the program has to read the numbers N and S, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

输出:

For each the case the program has to print the result on separate line of the output file.if no answer, print 0.

样例输入:

2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

样例输出:

2
3

解题代码:

import java.util.Arrays;
import java.util.Scanner;

public class Main {

//	private static int ans[] =new int[100000];
	private static int index = 0;
	public static void get(int[] seq, int s , int[]ans) {
		int sum = 0;
	    int k = 0;
	    int len = 0;
		for (int i = 0 ; i = s){
				for(int j = k ;j< i;j++ ){
					int temp = sum - seq[j];
					if(temp >= s){
						sum = temp;
						len --;
					}else{
						k = j;
						ans[index++] = len;
						break;
					}
				}
			}
				
		}
	}

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int testNum = sc.nextInt();

		for (int i = 0; i < testNum; i++) {
			
			int n = sc.nextInt();
			int s = sc.nextInt();
			int[] seq = new int[n];
            int[] ans = new int[n];
            index = 0;
			for (int j = 0; j < n; j++) {
				seq[j] = sc.nextInt();
			}
			get(seq, s , ans);
			//Arrays.sort(seq);
	        Arrays.sort(ans , 0 ,index);
	        System.out.println(ans[0]);
		}

	}

}

  1. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。