2013
11-12

# 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]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */"
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;
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++)
{
//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;
}
{
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，比楼主的要快。