var a,c:array[1..100000] of string；
b,d:array[1..100000] of longint；
i,j,m,x,n,p:longint；st,s:string；
procedure qsort(l,r:longint)；
var
i,j,lll:longint；
yyy,xx:string；
begin
i:=l；j:=r；
xx:=a[(l+r) div 2]；
repeat
while a[i]<xx do inc(i)；
while a[j]>xx do dec(j)；
if i<=j then
begin
yyy:=a[i]；
a[i]:=a[j]；
a[j]:=yyy；
lll:=b[i]；
b[i]:=b[j]；
b[j]:=lll；
inc(i)；
dec(j)；
end；
until i>j；
if l<j then qsort(l,j)；
if i<r then qsort(i,r)；
end；
begin
readln(m,n)； readln(st)；
for i:=2 to m do begin
readln(s)；if st>s then st:=s；end；
for i:=1 to n do begin
readln(a[i])；
readln(b[i])；
end；
qsort(1,n)；
for i:=1 to n do
if a[i]=a[i-1] then x:=x+b[i] else
if a[i]<>a[i-1] then begin inc(p)；
c[p]:=a[i-1]；d[p]:=x；x:=b[i]；
end；
x:=-126630101；
for i:=1 to p do
if d[i]>x then begin
x:=d[i]；s:=c[i]；end；
if d[i]<=0 then write(st)
else write(s)；
end.
测评机： Xeost[5]
得分： 70分
提交日期： 2009-10-21 18:54:00
有效耗时： 1515毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时172ms
测试结果3: 通过本测试点|有效耗时156ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时171ms
测试结果6: 测试结果错误.错误结果为:aaakutdo
正确结果应为:gazxlk
测试结果7: 测试结果错误.错误结果为:aacdor
正确结果应为:imxygcbrvs
测试结果8: 通过本测试点|有效耗时297ms
测试结果9: 通过本测试点|有效耗时375ms
测试结果10: 测试结果错误.错误结果为:aaafoiok
正确结果应为:mfgfjklulo
var
st:string；
i,j,k,m,n:longint；
na:array[1..100000]of string；
sz:array[1..100000]of longint；
function find(s:string):longint；
var
l,r,mid:longint；
begin
l:=1； r:=n；
mid:=(l+r) div 2；
while na[mid]<>s do
begin
if na[mid]>s then r:=mid-1
else if na[mid]<s then l:=mid+1；
mid:=(l+r) div 2；
end；
exit(mid)；
end；
procedure naqsort(l,r:longint)；
var
i,j:longint；
xx,ss:string；
begin
i:=l； j:=r；
xx:=na[random(r-l+1)+l]；
repeat
while na[i]<xx do inc(i)；
while na[j]>xx do dec(j)；
if i<=j then
begin
ss:=na[i]；
na[i]:=na[j]；
na[j]:=ss；
inc(i)；
dec(j)；
end；
until i>j；
if l<j then naqsort(l,j)；
if i<r then naqsort(i,r)；
end；
procedure qsort(l,r:longint)；
var
i,j,p,x,y:longint；
xx,ss:string；
begin
i:=l； j:=r；
p:=random(r-l+1)+l；
xx:=na[p]；
x:=sz[p]；
repeat
while (sz[i]>x)or((sz[i]=x)and(na[i]<xx)) do inc(i)；
while (sz[j]<x)or((sz[j]=x)and(na[j]>xx)) do dec(j)；
if i<=j then
begin
ss:=na[i]；
na[i]:=na[j]；
na[j]:=ss；
y:=sz[i]；
sz[i]:=sz[j]；
sz[j]:=y；
inc(i)；
dec(j)；
end；
until i>j；
if l<j then qsort(l,j)；
if i<r then qsort(i,r)；
end；
begin
randomize；
fillchar(sz,sizeof(sz),0)；
readln(n,m)；
for i:=1 to n do readln(na[i])；
naqsort(1,n)；
for j:=1 to m do
begin
readln(st)；
readln(k)；
inc(sz[find(st)],k)；
end；
qsort(1,n)；
writeln(na[1])；
end.
自己对比一下~~
i,n,m,v,max:longint；
ss:string；
s:array[1..100010] of string；
f:array[1..100010] of longint；
procedure Qsort(l,r:longint)；
var i,j:longint；t,k:string；
begin
i:=l；j:=r；k:=s[(j+i) div 2]；
repeat
while k<s[j] do dec(j)；
while s[i]<k do inc(i)；
if i<=j then begin
t:=s[i]；s[i]:=s[j]；s[j]:=t；
inc(i)；dec(j)；
end；
until i>j；
if l<j then Qsort(l,j)；
if i<r then Qsort(i,r)；
end；
function Find(now:string；i,j:longint):longint；
var mid:longint；
begin
mid:=(j+i) shr 1；
if (now=s[mid]) then exit(mid)
else if (now>s[mid]) then exit(find(now,mid+1,j))
else exit(find(now,i,mid-1))；
end；
begin
fillchar(f,sizeof(f),0)；
readln(n,m)；
for i:=1 to n do readln(s[i])；
Qsort(1,n)；
for i:=1 to m do begin
readln(ss)；
readln(v)；
inc(f[Find(ss,0,n)],v)；
end；
max:=0；
for i := 1 to n do
if (max<f[i]) or ((max=f[i])and(s[i]<ss)) then begin
max:=f[i]；
ss:=s[i]；
end；
writeln(ss)；
end.
s[i]为人名，f[i]记录该人的值。
先排序再二分查找
最后从头到尾扫一遍，找最大值
只用排有RP变化的人的名字
也就是:
readln(m,n)；
for i:=1 to m do
readln(s)；
直接可以忽略
根本就不用2分
也不用HASH
var a,c:array[1..100000] of string；
b,d:array[1..100000] of longint；
i,j,m,k,n,p:longint；st,s:string；
procedure qsort(l,r:longint)；
var
i,j,lll:longint；
y,x:string；
begin
i:=l；j:=r；
x:=a[(l+r) div 2]；
repeat
while a[i]<x do inc(i)；
while a[j]>x do dec(j)；
if i<=j then
begin
y:=a[i]；
a[i]:=a[j]；
a[j]:=y；
lll:=b[i]；
b[i]:=b[j]；
b[j]:=lll；
inc(i)；
dec(j)；
end；
until i>j；
if l<j then qsort(l,j)；
if i<r then qsort(i,r)；
end；
begin
readln(m,n)；
for i:=1 to m do
readln(s)；
for i:=1 to n do begin
readln(a[i])；
if k<length(a[i]) then k:=length(a[i])；
readln(b[i])；
end；
for i:=1 to n do
while length(a[i])<k do a[i]:=’ ’+a[i]；
qsort(1,n)；
for i:=1 to n do
if a[i]=a[i-1] then x:=x+b[i] else
if a[i]<>a[i-1] then begin inc(p)；
c[p]:=a[i-1]；d[p]:=x；x:=b[i]；
end；
x:=-maxlongint；
for i:=1 to p do
if d[i]>x then begin
x:=d[i]；s:=c[i]；end；
while s[1]=’ ’ do delete(s,1,1)；
writeln(s)；
end.
测评机： Xeost[5]
得分： 100分
提交日期： 2009-10-28 17:26:00
有效耗时： 2268毫秒
测试结果1: 通过本测试点|有效耗时156ms
测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时157ms
测试结果4: 通过本测试点|有效耗时172ms
测试结果5: 通过本测试点|有效耗时172ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 通过本测试点|有效耗时188ms
测试结果8: 通过本测试点|有效耗时282ms
测试结果9: 通过本测试点|有效耗时375ms
测试结果10: 通过本测试点|有效耗时407ms