首页 > 专题系列 > Java解POJ > POJ 3017 Cut the Sequence [解题报告] Java
2013
11-12

POJ 3017 Cut the Sequence [解题报告] Java

Cut the Sequence

问题描述 :

Given an integer sequence { an } of length N, you are to cut the sequence into several parts every one of which is a consecutive subsequence of the original sequence. Every part must satisfy that the sum of the integers in the part is not greater than a given integer M. You are to find a cutting that minimizes the sum of the maximum integer of each part.

输入:

The first line of input contains two integer N (0 < N ≤ 100 000), M. The following line contains N integers describes the integer sequence. Every integer in the sequence is between 0 and 1 000 000 inclusively.

输出:

Output one integer which is the minimum sum of the maximum integer of each part. If no such cuttings exist, output −1.

样例输入:

8 17
2 2 2 8 1 8 2 1

样例输出:

12

温馨提示:

Use 64-bit integer type to hold M.

解题代码:

//* @author: Yeming Hu"[email protected]"
import java.util.*;
import java.io.*;

public class Main {
  
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        Container cn= new Container();
        boolean noSuchCut =false;
        int n = sc.nextInt();
        long m = sc.nextLong();
        Wrapper[] sequence = new Wrapper[n+1];
        sequence[0] = new Wrapper();
        sequence[0].opt = 0;
        sequence[0].num = 0;
        sequence[0].sum = 0;
        sequence[0].k = 0;
        sequence[0].l = 0;
        cn.add(sequence[0]);
        for(int i = 1; i < n+1; i++)
        {
            sequence[i] = new Wrapper();
            sequence[i].num = sc.nextLong();
            if(sequence[i].num > m)
            {
                noSuchCut = true;
            }
            sequence[i].sum += sequence[i].num + sequence[i-1].sum;
            sequence[i].k = i;
        }
        if(noSuchCut)
        {
            System.out.println(-1);
        }else
        {
        int p = n-1;
        int i;
        boolean first =false;
        for(i = n; i >=1; i--)
        {
            for(int j = p; j >= 0; j--)
            {
                if(sequence[i].sum - sequence[j].sum > m)
                {
                    sequence[i].l = j+2;
                    p = j;
                    break;
                }else if(j == 0)
                {
                    sequence[i].l = 1;
                    p = j;
                    first =true;
                    break;
                }
            }
            if(p == 0 && first)
            {
                break;
            }
        }
       
        for(int j = i - 1; j >= 1; j--)
        {
            sequence[j].l = 1;
        }
        /*
        for(int j = 0; j < n+1; j++)
        {
            System.out.println(sequence[j]);
        }
        */
        for(i = 1; i < n+1; i++)
        {
            cn.add(sequence[i]);
            //System.out.println("----");
            //System.out.println(cn);
            //System.out.println("----");
            long min = sequence[sequence[i].l-1].opt + cn.array[cn.s].num;
            //System.out.println(min);
            for(int j = cn.s; j < cn.e-1; j++)
            {
                long temp = cn.array[j].opt + cn.array[j+1].num;
                if(temp < min)
                {
                    min = temp;
                }
            }
            sequence[i].opt = min;
            //System.out.println(min);
        }  
        System.out.println(sequence[n].opt);
    }
    }
    
}

class Wrapper implements Comparable< Wrapper>
{
    long opt;
    long num;
    long sum;
    int l;
    int k;
    
    public int compareTo(Wrapper w)
    {
        if(this.num == w.num)
        {
            return 0;
        }else if(this.num > w.num)
        {
            return -1;
        }else
        {
            return 1;
        }
    }
    public String toString()
    {
        return "opt:" + opt + " num:" + num + " sum:" + sum +
                " l:" + l + " k:" + k;
    }
}
class Container
{
    Wrapper[] array;
    int s , e;
    public Container()
    {
        array = new Wrapper[100008];
        s = 0;
        e = 0;
    }
    public void add(Wrapper w)
    {
        int i;
        for(i = s; i < e; i++)
        {
            if(array[i].k >= w.l)
            {
                break;
            }
        }
        s = i;
        for(i = e-1; i >= s; i-- )
        {
            if(array[i].compareTo(w) == -1)
            {
                break;
            }
        }
        array[i+1] = w;
        e = i+2;
    }
    public String toString()
    {
        String result = "";
        for(int i = s; i < e; i++)
        {
            result += array[i].num + " "; 
        }
        return result;
    }
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。