- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在解决 this problem通过使用线段树。我在每个节点保存总和、最大值、最左边的最大值和最右边的最大值。然后我搜索图表以找到特定时间间隔的答案。我怎样才能提高这段代码的速度?
import java.util.Scanner;
//TLE
class GSS1 {
static class Node{
int max;
int MaxL;
int MaxR;
int sum;
public Node(int max, int MaxL, int MaxR, int sum){
this.max=max;
this.MaxL=MaxL;
this.MaxR=MaxR;
this.sum=sum;
}
public Node(){
}
}
static class SegmentTree{
private Node[] tree;
private int maxsize;
private int height;
private final int STARTINDEX = 0;
private final int ENDINDEX;
private final int ROOT = 0;
Node s;
public SegmentTree(int size){
height = (int)(Math.ceil(Math.log(size) / Math.log(2)));
maxsize = 2 * (int) Math.pow(2, height) - 1;
tree = new Node[maxsize];
for(int i=0;i<tree.length;i++){
tree[i]=new Node();
}
ENDINDEX = size - 1;
s=new Node();
s.MaxL=Integer.MIN_VALUE;
s.MaxR=Integer.MIN_VALUE;
s.sum=Integer.MIN_VALUE;
s.max=Integer.MIN_VALUE;
}
private int leftchild(int pos){
return 2 * pos + 1;
}
private int rightchild(int pos){
return 2 * pos + 2;
}
private int mid(int start, int end){
return (start + (end - start) / 2);
}
private Node constructSegmentTreeUtil(int[] elements, int startIndex, int endIndex, int current){
if (startIndex == endIndex)
{
tree[current].max=tree[current].MaxL=tree[current].MaxR=tree[current].sum=elements[startIndex];
return tree[current];
}
int mid = mid(startIndex, endIndex);
Node left=constructSegmentTreeUtil(elements, startIndex, mid, leftchild(current));
Node right=constructSegmentTreeUtil(elements, mid + 1, endIndex, rightchild(current));
tree[current].max = Math.max(left.max, right.max);
tree[current].MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
tree[current].MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
tree[current].sum = left.sum+right.sum;
return tree[current];
}
public void constructSegmentTree(int[] elements){
constructSegmentTreeUtil(elements, STARTINDEX, ENDINDEX, ROOT);
}
private Node getSumUtil(int startIndex, int endIndex, int queryStart, int queryEnd, int current){
if (queryStart <= startIndex && queryEnd >= endIndex ){
return tree[current];
}
if (endIndex < queryStart || startIndex > queryEnd){
return s;
}
int mid = mid(startIndex, endIndex);
Node left=getSumUtil(startIndex, mid, queryStart, queryEnd, leftchild(current));
Node right=getSumUtil( mid + 1, endIndex, queryStart, queryEnd, rightchild(current));
Node current_Node=new Node();
current_Node.max = Math.max(left.max, right.max);
current_Node.MaxL = Math.max(left.MaxL , left.sum+right.MaxL);
current_Node.MaxR = Math.max(right.MaxR , right.sum+left.MaxR);
current_Node.sum = left.sum+right.sum;
return current_Node;
}
public int getMaxSum(int queryStart, int queryEnd){
if(queryStart < 0 || queryEnd > tree.length)
{System.out.println("inside negative");
return Integer.MIN_VALUE;
}
return getMax(getSumUtil(STARTINDEX, ENDINDEX, queryStart, queryEnd, ROOT));
}
public int getMax(Node r){
return Math.max(Math.max(r.max, r.MaxL),Math.max(r.MaxR, r.sum));
}
public int getFirst(){
return tree[0].MaxL;
}
}
public static void main(String[] args) {
Scanner input=new Scanner(System.in);
int numbers[]=new int [input.nextInt()];
for(int i=0;i<numbers.length;i++){
numbers[i]=input.nextInt();
}
SegmentTree tree=new SegmentTree(numbers.length);
tree.constructSegmentTree(numbers);
int cases=input.nextInt();
int x;
int y;
int query;
for(int i=0;i<cases;i++){
x=input.nextInt()-1;
y=input.nextInt()-1;
System.out.println(tree.getMaxSum(x, y));
}
}
}
最佳答案
您的方法是正确的,但 I/O 速度对于这个问题也很重要,因为时间限制非常严格。您应该使用自定义阅读器,因为 Scanner
非常慢。使用下面提到的类来读取输入。
class Reader {
final private int BUFFER_SIZE = 1 << 16;private DataInputStream din;private byte[] buffer;private int bufferPointer, bytesRead;
public Reader(){din=new DataInputStream(System.in);buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
}public Reader(String file_name) throws IOException{din=new DataInputStream(new FileInputStream(file_name));buffer=new byte[BUFFER_SIZE];bufferPointer=bytesRead=0;
}public String readLine() throws IOException{byte[] buf=new byte[64];int cnt=0,c;while((c=read())!=-1){if(c=='\n')break;buf[cnt++]=(byte)c;}return new String(buf,0,cnt);
}public int nextInt() throws IOException{int ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
}public long nextLong() throws IOException{long ret=0;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c=read();do{ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(neg)return -ret;return ret;
}public double nextDouble() throws IOException{double ret=0,div=1;byte c=read();while(c<=' ')c=read();boolean neg=(c=='-');if(neg)c = read();do {ret=ret*10+c-'0';}while((c=read())>='0'&&c<='9');if(c=='.')while((c=read())>='0'&&c<='9')ret+=(c-'0')/(div*=10);if(neg)return -ret;return ret;
}private void fillBuffer() throws IOException{bytesRead=din.read(buffer,bufferPointer=0,BUFFER_SIZE);if(bytesRead==-1)buffer[0]=-1;
}private byte read() throws IOException{if(bufferPointer==bytesRead)fillBuffer();return buffer[bufferPointer++];
}public void close() throws IOException{if(din==null) return;din.close();}
}
关于java - GSS1 -SPOJ - 线段树 TLE,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/23377354/
有没有办法将多个线段视为 1 条线? IE:我将鼠标悬停在其中一个上,两者都会突出显示,并且切换图例中的可见性将隐藏这两个部分。 http://jsfiddle.net/rayholland/HSvB
有没有办法将多条线段视为一条线? IE:我将鼠标悬停在一个上,两个都突出显示,切换图例中的可见性将隐藏两个部分。 http://jsfiddle.net/rayholland/HSvBj/2/ ser
我正在尝试解决有关使用箭头键绘制线条的练习。当按下任一箭头键时,该线从中心开始向东、西、北或南绘制。该代码仅在东或西方向有效,而在北或南方向无效,这是我的问题!! 有人可以给我关于这件事的想法吗?谢谢
给定每条线的起点和终点的 XYZ 坐标,如何确定两条 3D 线段是否相交?如果它们确实相交,在什么 XYZ 位置? 我只能找到 2D 的答案:How do you detect where two l
给定每条线的起点和终点的 XYZ 坐标,如何确定两条 3D 线段是否相交?如果它们确实相交,在什么 XYZ 位置? 我只能找到 2D 的答案:How do you detect where two l
我正在使用适用于 ios 的 google map sdk 来提供当前用户位置和结束位置之间的方向。到目前为止,我已经使用下面的代码在当前用户位置和结束位置之间绘制了一条 GMSPolyline,并且
我是 Qt 的新手,我想使用 Qt 使用 CGAL 制作交互式几何程序。我希望用户使用鼠标输入点、线段,然后按下按钮让 CGAL 算法处理输入。 我的环境是 CGAL 4.5、Qt 5.6 和 QtC
我有两条线段:X1,Y1,Z1 - X2,Y2,Z2 和 X3,Y3,Z3 - X4,Y4,Z4 我试图找到两个线段之间的最短距离。 几个小时以来,我一直在寻找解决方案,但所有这些解决方案似乎都适用于
我正在尝试在 WPF 中创建铁路轨道和带有边界和标签的街道等效果。如何向线段添加边框和沿线段的标签?我试过 Border 类,但它创建了一个矩形边框。 对于标签,我尝试了 Text on a path
我正在做一个小项目来显示基于路线段重叠的路线效率低下。 例如,我在这里放了一个 JSFIDDLE,显示 D 和 E 之间有一条粉红色和蓝色的线重叠。我如何确定这段路在它们的路线上有重叠? 路线将由用户
我想绘制三组数据。具体来说,我想显示单个数据点,包括三组的均值。这是我到目前为止所拥有的: library(ggplot2) df <- data.frame(group=rep(c("A", "B"
我想绘制三组数据。具体来说,我想显示单个数据点,包括三组的均值。这是我到目前为止所拥有的: library(ggplot2) df <- data.frame(group=rep(c("A", "B"
<line> 元素可以用来画线段 SVG 线段 <line> <line> 元素可以用来画线段 线段的起始坐标可以用 x1 和 y1 来定义 线段的终点坐标可
我正在我的游戏中编写 C++ 碰撞检测程序,并试图提出一种算法:我有一个由两个中心点(C1、C2)、长度和半径定义的胶囊。然后我有一条用两点(R1,R2)定义的射线。我已经知道它们相交了。我只需要找到
我正在创建一个包含多变量数据的 PCA 双图。 有没有办法在 ggbiplot 中指定线段的颜色/透明度/位置?此命令的所有参数均未提供此选项。 我知道 ggbiplot 是基于 ggplot - 它
最近学了下 python opencv,分享下使用 opencv 在图片上绘制常用图形的方法。 案例中实现了在图片中添加线段、圆形、矩形、椭圆形以及添加文字的方法,使用 opencv2 实现的
我在应用 rgl 3d 绘图包时遇到了一些问题。 我正在尝试绘制一些线段。我的数据被安排在一个名为“标记”的数据框中,它有六列,一列代表起始 x、y 和 z 值,一列代表结束 x、y 和 z 值。 s
我必须使用 matplotlib 库绘制多条“曲线”,每条曲线由水平线段(甚至点)组成。 我通过 NaNs 分隔片段达到了这个目标。这是我的示例(工作)代码: from pylab import ar
我是一名优秀的程序员,十分优秀!