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