不过这个是百度之星题目吗？百度之星又不是你评的。
先占个位置，以后将答案补上！
其实做出来挺简单，做好就难，主要那个排序算法要优化。
今天比较亏，这个10分的题目花了半天！
读入一个二维数组，在读入的时候进行粗排序。
对这个数组按dat(0 ，i) (跨度) 进行排序
dim JG(1 to 5) as long
对排序后的数据进行处理
先对最后的10个元素进行比较，选出最大的重叠区；
再去掉前面跨度小于最大重叠区的；
剩下的很少了
基本上不超过10个元素，很有可能就1个；
在剩下的里面找最大重叠区；
排序的算法优化问题！
程序编得比较复杂，主要是为了占用内存少和速度快，运行起来内存需要15M左右，排序算法我自己设计的，思路是N+1位数肯定大于N位数，效果很好，50万个二维元素排序大概在15秒左右，
总共20秒不到；
CPU：Athlon xp 64位 2800+，超频到2.25G，而且在听歌和上QQ。
Private Dat() As Long
Private DatCount As Long
Private JG(1 To 5) As Long
Private tm1 As Date, tm2 As Date
Private Sub Command1_Click()
Dim Dat1() As Long
Dim Dat2() As Long
Dim Dat3() As Long
Dim Dat4() As Long
Dim Dat5() As Long
Dim Dat6() As Long
Dim Dat7() As Long
Dim Dat8() As Long
Dim Dat9() As Long
Dim Dat10() As Long
Dim MaxCD As Long
Dim N(1 To 10) As Long
Dim a As Long, b As Long, i As Long, j As Long, k As Long
'以下代码读入并粗排序
Open App.Path + "\input.txt" For Input As #1
j = 0
Do Until EOF(1)
Input #1, a, b
j = j + 1
i = i + 1
Select Case Abs(b - a)
Case Is >1000000000
k = 10
N(k) = N(k) + 1
ReDim Preserve Dat10(0 To 3, 1 To N(k)) As Long
Dat10(0, N(k)) = Abs(b - a)
Dat10(1, N(k)) = a
Dat10(2, N(k)) = b
Dat10(3, N(k)) = Abs(b - a)
Case Is >100000000
k = 9
N(k) = N(k) + 1
ReDim Preserve Dat9(0 To 3, 1 To N(k)) As Long
Dat9(0, N(k)) = Abs(b - a)
Dat9(1, N(k)) = a
Dat9(2, N(k)) = b
Dat9(3, N(k)) = Abs(b - a)
Case Is >10000000
k = 8
N(k) = N(k) + 1
ReDim Preserve Dat8(0 To 3, 1 To N(k)) As Long
Dat8(0, N(k)) = Abs(b - a)
Dat8(1, N(k)) = a
Dat8(2, N(k)) = b
Dat8(3, N(k)) = Abs(b - a)
Case Is >1000000
k = 7
N(k) = N(k) + 1
ReDim Preserve Dat7(0 To 3, 1 To N(k)) As Long
Dat7(1, N(k)) = a
Dat7(3, N(k)) = Abs(b - a)
Dat7(0, N(k)) = Abs(b - a)
Dat7(2, N(k)) = b
Case Is >100000
k = 6
N(k) = N(k) + 1
ReDim Preserve Dat6(0 To 3, 1 To N(k)) As Long
Dat6(0, N(k)) = Abs(b - a)
Dat6(1, N(k)) = a
Dat6(2, N(k)) = b
Dat6(3, N(k)) = Abs(b - a)
Case Is >10000
k = 5
N(k) = N(k) + 1
ReDim Preserve Dat5(0 To 3, 1 To N(k)) As Long
Dat5(0, N(k)) = Abs(b - a)
Dat5(1, N(k)) = a
Dat5(2, N(k)) = b
Dat5(3, N(k)) = Abs(b - a)
Case Is >1000
k = 4
N(k) = N(k) + 1
ReDim Preserve Dat4(0 To 3, 1 To N(k)) As Long
Dat4(0, N(k)) = Abs(b - a)
Dat4(1, N(k)) = a
Dat4(2, N(k)) = b
Dat4(3, N(k)) = Abs(b - a)
Case Is >100
k = 3
N(k) = N(k) + 1
ReDim Preserve Dat3(0 To 3, 1 To N(k)) As Long
Dat3(0, N(k)) = Abs(b - a)
Dat3(1, N(k)) = a
Dat3(2, N(k)) = b
Dat3(3, N(k)) = Abs(b - a)
Case Is >10
k = 2
N(k) = N(k) + 1
ReDim Preserve Dat2(0 To 3, 1 To N(k)) As Long
Dat2(0, N(k)) = Abs(b - a)
Dat2(1, N(k)) = a
Dat2(2, N(k)) = b
Dat2(3, N(k)) = Abs(b - a)
Case Else
k = 1
N(k) = N(k) + 1
ReDim Preserve Dat1(0 To 3, 1 To N(k)) As Long
Dat1(0, N(k)) = Abs(b - a)
Dat1(1, N(k)) = a
Dat1(2, N(k)) = b
Dat1(3, N(k)) = Abs(b - a)
End Select
Loop
Close #1
ReDim Preserve Dat(0 To 2, 1 To j) As Long
'排序
tm1 = Now
DatCount = 0
PX Dat1, N(1), 1
PX Dat2, N(2), 2
PX Dat3, N(3), 3
PX Dat4, N(4), 4
PX Dat5, N(5), 5
PX Dat6, N(6), 6
PX Dat7, N(7), 7
PX Dat8, N(8), 8
PX Dat9, N(9), 9
PX Dat10, N(10), 10
MsgBox Now - tm1
'顺序合并到Dat数组
'1
For i = 1 To N(1)
Dat(0, DatCount + i) = Dat1(0, i)
Dat(1, DatCount + i) = Dat1(1, i)
Dat(2, DatCount + i) = Dat1(2, i)
Next i
DatCount = DatCount + N(1)
'2
For i = 1 To N(2)
Dat(1, DatCount + i) = Dat2(1, i)
Dat(0, DatCount + i) = Dat2(0, i)
Dat(2, DatCount + i) = Dat2(2, i)
Next i
DatCount = DatCount + N(2)
'3
For i = 1 To N(3)
Dat(1, DatCount + i) = Dat3(1, i)
Dat(0, DatCount + i) = Dat3(0, i)
Dat(2, DatCount + i) = Dat3(2, i)
Next i
DatCount = DatCount + N(3)
'4
For i = 1 To N(4)
Dat(1, DatCount + i) = Dat4(1, i)
Dat(0, DatCount + i) = Dat4(0, i)
Dat(2, DatCount + i) = Dat4(2, i)
Next i
DatCount = DatCount + N(4)
'5
For i = 1 To N(5)
Dat(0, DatCount + i) = Dat5(0, i)
Dat(1, DatCount + i) = Dat5(1, i)
Dat(2, DatCount + i) = Dat5(2, i)
Next i
DatCount = DatCount + N(5)
'6
For i = 1 To N(6)
Dat(0, DatCount + i) = Dat6(0, i)
Dat(1, DatCount + i) = Dat6(1, i)
Dat(2, DatCount + i) = Dat6(2, i)
Next i
DatCount = DatCount + N(6)
'7
For i = 1 To N(7)
Dat(0, DatCount + i) = Dat7(0, i)
Dat(1, DatCount + i) = Dat7(1, i)
Dat(2, DatCount + i) = Dat7(2, i)
Next i
DatCount = DatCount + N(7)
'8
For i = 1 To N(8)
Dat(0, DatCount + i) = Dat8(0, i)
Dat(1, DatCount + i) = Dat8(1, i)
Dat(2, DatCount + i) = Dat8(2, i)
Next i
DatCount = DatCount + N(8)
'9
For i = 1 To N(9)
Dat(0, DatCount + i) = Dat9(0, i)
Dat(1, DatCount + i) = Dat9(1, i)
Dat(2, DatCount + i) = Dat9(2, i)
Next i
DatCount = DatCount + N(9)
'10
For i = 1 To N(10)
Dat(0, DatCount + i) = Dat10(0, i)
Dat(1, DatCount + i) = Dat10(1, i)
Dat(2, DatCount + i) = Dat10(2, i)
Next i
DatCount = DatCount + N(10)
'Open App.Path + "\output.txt" For Output As #2
'For i = 1 To DatCount
'Print #2, Dat(1, i), Dat(2, i)
'Next i
'Close #2
'处理
MaxCD = 0
tm1 = Now
'提取最后10的重叠最大值
JG(1) = 0
For i = DatCount - 9 To DatCount - 1
For j = i + 1 To DatCount
If GetCD(i, j) >MaxCD Then
MaxCD = GetCD(i, j)
JG(1) = MaxCD
JG(2) = Dat(1, DatCount - 1)
JG(3) = Dat(2, DatCount - 1)
JG(4) = Dat(1, DatCount)
JG(5) = Dat(2, DatCount)
End If
Next j
Next i
j = 0
k = 0
Do Until MaxCD \ 10 ^ j <10
k = k + N(j + 1)
j = j + 1
Loop
Do Until Dat(0, k) >= MaxCD
k = k + 1
Loop
'到目前为止，已经去掉大部分了
For i = k To DatCount - 1
For j = k + 1 To DatCount
k = GetCD(i, j)
If k >MaxCD Then
JG(1) = k
JG(2) = Dat(1, i)
JG(3) = Dat(2, i)
JG(4) = Dat(1, j)
JG(5) = Dat(2, j)
MaxCD = k
End If
Next j
Next i
'JG (1) 就是要的数据
tm2 = Now
MsgBox tm2 - tm1, , JG(1)
End Sub
Private Function GetCD(ByVal N1 As Long, ByVal N2 As Long) As Long
Dim a(1 To 2) As Long
Dim b(1 To 2) As Long
Dim c(1 To 2) As Long
If Dat(1, N1) <Dat(2, N1) Then
a(1) = Dat(1, N1)
a(2) = Dat(2, N1)
Else
a(1) = Dat(2, N1)
a(2) = Dat(1, N1)
End If
If Dat(1, N2) <Dat(2, N2) Then
b(1) = Dat(1, N2)
b(2) = Dat(2, N2)
Else
b(1) = Dat(2, N2)
b(2) = Dat(1, N2)
End If
If a(1) >b(1) Then
c(1) = a(1)
Else
c(1) = b(1)
End If
If a(2) <b(2) Then
c(2) = a(2)
Else
c(2) = b(2)
End If
GetCD = c(2) - c(1)
End Function
Private Sub PX(ByRef X() As Long, ByVal Xcount As Long, ByVal Ns As Long)
On Error GoTo PXerr
Dim Dt0() As Long
Dim Dt1() As Long
Dim Dt2() As Long
Dim Dt3() As Long
Dim Dt4() As Long
Dim Dt5() As Long
Dim Dt6() As Long
Dim Dt7() As Long
Dim Dt8() As Long
Dim Dt9() As Long
Dim Nk(0 To 9) As Long, k As Long
If Xcount = 0 Then Exit Sub
If Ns = 0 Then Exit Sub
For i = 1 To Xcount
Select Case X(3, i) \ 10 ^ (Ns - 1)
Case Is = 0
Nk(0) = Nk(0) + 1
ReDim Preserve Dt0(0 To 3, 1 To Nk(0)) As Long
Dt0(0, Nk(0)) = X(0, i)
Dt0(1, Nk(0)) = X(1, i)
Dt0(2, Nk(0)) = X(2, i)
Dt0(3, Nk(0)) = X(3, i)
Case Is = 1
Nk(1) = Nk(1) + 1
ReDim Preserve Dt1(0 To 3, 1 To Nk(1)) As Long
Dt1(0, Nk(1)) = X(0, i)
Dt1(1, Nk(1)) = X(1, i)
Dt1(2, Nk(1)) = X(2, i)
Dt1(3, Nk(1)) = X(3, i) - 1 * 10 ^ (Ns - 1)
Case Is = 2
Nk(2) = Nk(2) + 1
ReDim Preserve Dt2(0 To 3, 1 To Nk(2)) As Long
Dt2(0, Nk(2)) = X(0, i)
Dt2(1, Nk(2)) = X(1, i)
Dt2(2, Nk(2)) = X(2, i)
Dt2(3, Nk(2)) = X(3, i) - 2 * 10 ^ (Ns - 1)
Case Is = 3
Nk(3) = Nk(3) + 1
ReDim Preserve Dt3(0 To 3, 1 To Nk(3)) As Long
Dt3(0, Nk(3)) = X(0, i)
Dt3(1, Nk(3)) = X(1, i)
Dt3(2, Nk(3)) = X(2, i)
Dt3(3, Nk(3)) = X(3, i) - 3 * 10 ^ (Ns - 1)
Case Is = 4
Nk(4) = Nk(4) + 1
ReDim Preserve Dt4(0 To 3, 1 To Nk(4)) As Long
Dt4(0, Nk(4)) = X(0, i)
Dt4(1, Nk(4)) = X(1, i)
Dt4(2, Nk(4)) = X(2, i)
Dt4(3, Nk(4)) = X(3, i) - 4 * 10 ^ (Ns - 1)
Case Is = 5
Nk(5) = Nk(5) + 1
ReDim Preserve Dt5(0 To 3, 1 To Nk(5)) As Long
Dt5(0, Nk(5)) = X(0, i)
Dt5(1, Nk(5)) = X(1, i)
Dt5(2, Nk(5)) = X(2, i)
Dt5(3, Nk(5)) = X(3, i) - 5 * 10 ^ (Ns - 1)
Case Is = 6
Nk(6) = Nk(6) + 1
ReDim Preserve Dt6(0 To 3, 1 To Nk(6)) As Long
Dt6(0, Nk(6)) = X(0, i)
Dt6(1, Nk(6)) = X(1, i)
Dt6(2, Nk(6)) = X(2, i)
Dt6(3, Nk(6)) = X(3, i) - 6 * 10 ^ (Ns - 1)
Case Is = 7
Nk(7) = Nk(7) + 1
ReDim Preserve Dt7(0 To 3, 1 To Nk(7)) As Long
Dt7(0, Nk(7)) = X(0, i)
Dt7(1, Nk(7)) = X(1, i)
Dt7(2, Nk(7)) = X(2, i)
Dt7(3, Nk(7)) = X(3, i) - 7 * 10 ^ (Ns - 1)
Case Is = 8
Nk(8) = Nk(8) + 1
ReDim Preserve Dt8(0 To 3, 1 To Nk(8)) As Long
Dt8(0, Nk(8)) = X(0, i)
Dt8(1, Nk(8)) = X(1, i)
Dt8(2, Nk(8)) = X(2, i)
Dt8(3, Nk(8)) = X(3, i) - 8 * 10 ^ (Ns - 1)
Case Is = 9
Nk(9) = Nk(9) + 1
ReDim Preserve Dt9(0 To 3, 1 To Nk(9)) As Long
Dt9(0, Nk(9)) = X(0, i)
Dt9(1, Nk(9)) = X(1, i)
Dt9(2, Nk(9)) = X(2, i)
Dt9(3, Nk(9)) = X(3, i) - 9 * 10 ^ (Ns - 1)
End Select
Next i
'排序
PX Dt0, Nk(0), Ns - 1
PX Dt1, Nk(1), Ns - 1
PX Dt2, Nk(2), Ns - 1
PX Dt3, Nk(3), Ns - 1
PX Dt4, Nk(4), Ns - 1
PX Dt5, Nk(5), Ns - 1
PX Dt6, Nk(6), Ns - 1
PX Dt7, Nk(7), Ns - 1
PX Dt8, Nk(8), Ns - 1
PX Dt9, Nk(9), Ns - 1
'合并
Hb:
k = 0
'0
For i = 1 To Nk(0)
X(0, k + i) = Dt0(0, i)
X(1, k + i) = Dt0(1, i)
X(2, k + i) = Dt0(2, i)
X(3, k + i) = Dt0(3, i)
Next i
k = k + Nk(0)
'1
For i = 1 To Nk(1)
X(0, k + i) = Dt1(0, i)
X(1, k + i) = Dt1(1, i)
X(2, k + i) = Dt1(2, i)
X(3, k + i) = Dt1(3, i)
Next i
k = k + Nk(1)
'2
For i = 1 To Nk(2)
X(0, k + i) = Dt2(0, i)
X(1, k + i) = Dt2(1, i)
X(2, k + i) = Dt2(2, i)
X(3, k + i) = Dt2(3, i)
Next i
k = k + Nk(2)
'3
For i = 1 To Nk(3)
X(0, k + i) = Dt3(0, i)
X(1, k + i) = Dt3(1, i)
X(2, k + i) = Dt3(2, i)
X(3, k + i) = Dt3(3, i)
Next i
k = k + Nk(3)
'4
For i = 1 To Nk(4)
X(0, k + i) = Dt4(0, i)
X(1, k + i) = Dt4(1, i)
X(2, k + i) = Dt4(2, i)
X(3, k + i) = Dt4(3, i)
Next i
k = k + Nk(4)
'5
For i = 1 To Nk(5)
X(0, k + i) = Dt5(0, i)
X(1, k + i) = Dt5(1, i)
X(2, k + i) = Dt5(2, i)
X(3, k + i) = Dt5(3, i)
Next i
k = k + Nk(5)
'6
For i = 1 To Nk(6)
X(0, k + i) = Dt6(0, i)
X(1, k + i) = Dt6(1, i)
X(2, k + i) = Dt6(2, i)
X(3, k + i) = Dt6(3, i)
Next i
k = k + Nk(6)
'7
For i = 1 To Nk(7)
X(0, k + i) = Dt7(0, i)
X(1, k + i) = Dt7(1, i)
X(2, k + i) = Dt7(2, i)
X(3, k + i) = Dt7(3, i)
Next i
k = k + Nk(7)
'8
For i = 1 To Nk(8)
X(0, k + i) = Dt8(0, i)
X(1, k + i) = Dt8(1, i)
X(2, k + i) = Dt8(2, i)
X(3, k + i) = Dt8(3, i)
Next i
k = k + Nk(8)
'9
For i = 1 To Nk(9)
X(0, k + i) = Dt9(0, i)
X(1, k + i) = Dt9(1, i)
X(2, k + i) = Dt9(2, i)
X(3, k + i) = Dt9(3, i)
Next i
Exit Sub
PXerr:
Exit Sub
End Sub
#include"algorithm"#include"iostream"
#include"stdio.h"
#include"vector"
using namespace std
typedef vector<int>VI
int main()
{
int i,n,m,ans
VI array
while (scanf("%d",&n)!=EOF)
{
array.resize(n)
for(i=0i<ni++)
{
scanf("%d",&array[i])
}
scanf("%d",&m)
if(m==0)
{
printf("0\n")
return 0
}
int s,t
s=0
t=0
ans=n
for(i=0i<ni++)
{
t+=array[i]
if(t>m&&i-s<ans)
{
ans=i-s
}
while (t>=m)
{
if(t>=m&&i-s<ans)
{
ans=i-s
}
t-=array[s]
s++
}
}
printf("%d\n",ans)
}
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）