program exam;
var i,j,m,n,k,l:longint;
a,b,c,d,f:array[0..100000] of longint;
procedure qt(l,r:longint);
var i,j,m,p:longint;
begin
i:=l; j:=r;
m:=a[(l+r) div 2];
repeat
while a[i]>m do inc(i);
while a[j]<m do dec(j);
if i<=j then
begin
p:=a[i]; a[i]:=a[j]; a[j]:=p;
inc(i); dec(j);
end;
until i>j;
if i<r then qt(i,r);
if l<j then qt(l,j);
end;

procedure qt1(l,r:longint);
var i,j,m,p:longint;
begin
i:=l; j:=r;
m:=b[(l+r) div 2];
repeat
while b[i]>m do inc(i);
while b[j]<m do dec(j);
if i<=j then
begin
p:=b[i]; b[i]:=b[j]; b[j]:=p;
p:=c[i]; c[i]:=c[j]; c[j]:=p;
inc(i); dec(j);
end;
until i>j;
if i<r then qt1(i,r);
if l<j then qt1(l,j);
end;

begin
readln(n,m);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to m do
begin
c[i]:=i;
read(b[i]);
end;
qt(1,n);
qt1(1,m);
for i:=1 to m do
f[b[i]]:=i;
for i:=1 to m do
begin
while f[b[i]]<=n do
begin
inc(d[c[i]],a[f[b[i]]]);
inc(f[b[i]],m);
end;
end;
for i:=1 to m do
write(d[i],' ');
end.

纯粹模拟，对2个数组进行排序，然后模拟采摘结果，时间复杂度为o（n）对这个数据绝对秒杀。注意要用快排。或者堆排之类的。冒泡会爆炸吧。。。

然后按苹果一个个的枚举，从最高的淘淘分配下来，一直到所有苹果分配完毕。仔细点。这道题和很多题目差不多，主要是练你对排序的掌握程度。

###pascal code
program P1445;
type num=array[1..100000] of longint;
var a,data,ans,h:num;
i,j,n,m,k:longint;
pd:boolean;
procedure change(var xx,yy:longint);
var t:longint;
begin
t:=xx; xx:=yy; yy:=t;
end;

procedure qsort(l,r:longint; var x:num);
var i,mid,ll,rr:longint;
begin
ll:=l; rr:=r; mid:=x[(ll+rr) div 2];
repeat
while x[ll]>mid do inc(ll); while x[rr]<mid do dec(rr);
if ll<=rr then begin
change(x[ll],x[rr]); if pd=true then change(h[ll],h[rr]); inc(ll); dec(rr);
end;
until ll>rr;
if ll<r then qsort(ll,r,x);
if rr>l then qsort(l,rr,x);
end;

begin //main
fillchar(a,sizeof(a),0); fillchar(data,sizeof(data),0);
fillchar(ans,sizeof(ans),0); k:=0; pd:=false;
read(n,m);
for i:=1 to n do h[i]:=i;
for i:=1 to n do read(a[i]);
for i:=1 to m do read(data[i]);
qsort(1,n,a); pd:=true; qsort(1,m,data);
for i:=1 to n do
begin
inc(k); if k=m+1 then k:=1;
ans[h[k]]:=ans[h[k]]+a[i];
end;

for i:=1 to m do write(ans[i],' ');
end.

记录信息
评测状态 Runtime Error
题目 P1445 陶陶抢苹果
递交时间 2013-12-02 22:17:08
代码语言 C
评测机 VijosEx
消耗时间 0 ms
消耗内存 2472 KiB
评测时间 2013-12-02 22:17:08

评测结果
编译成功

foo.c: In function 'main':
foo.c:11:5: warning: format '%ld' expects argument of type 'long int *', but argument 2 has type 'int *' [-Wformat]
foo.c:14:5: warning: format '%ld' expects argument of type 'long int *', but argument 2 has type 'int *' [-Wformat]
foo.c:38:5: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'int' [-Wformat]

测试数据 #0: Accepted, time = 0 ms, mem = 444 KiB, score = 1

测试数据 #1: RuntimeError, time = 0 ms, mem = 440 KiB, score = 0

测试数据 #2: WrongAnswer, time = 0 ms, mem = 456 KiB, score = 0

测试数据 #3: WrongAnswer, time = 0 ms, mem = 484 KiB, score = 0

测试数据 #4: WrongAnswer, time = 0 ms, mem = 1424 KiB, score = 0

测试数据 #5: RuntimeError, time = 0 ms, mem = 2468 KiB, score = 0

测试数据 #6: RuntimeError, time = 0 ms, mem = 2472 KiB, score = 0

测试数据 #7: RuntimeError, time = 0 ms, mem = 2472 KiB, score = 0

测试数据 #8: RuntimeError, time = 0 ms, mem = 2468 KiB, score = 0

测试数据 #9: RuntimeError, time = 0 ms, mem = 2472 KiB, score = 0

RuntimeError, time = 0 ms, mem = 2472 KiB, score = 1

代码
#include <stdio.h>
#include <stdlib.h>
int cmp (const void *a,const void *b)
{return *(int )b-(int *)a;
}
int main (){
long n,m,i,j;
scanf ("%ld%ld",&n,&m);
int pg[n*n],tt[m*m],ttn[m*m],sum[m*m],new[m*m],maxn,cn,a=0,v,c;
for (i=0;i<n;i++)
{scanf ("%ld",&pg[i]);
}
for (i=0;i<m;i++)
{scanf ("%ld",&tt[i]);
sum[i]=0;
}
for (i=0;i<m;i++)
{maxn=-10000;
for (j=0;j<m;j++)
{if (tt[j]>maxn)
{maxn=tt[j];
cn=j;
}
}
new[a]=cn;
tt[j]=-100000;
}
qsort (pg,n,sizeof (pg[0]),cmp);
for (i=0;i<n;i++)
{v=i%m;
sum[v]+=pg[i];
}
for (i=0;i<m;i++)
{c=new[i];
ttn[c]=sum[i];
}
for (i=0;i<m;i++)
{printf ("%ld ",ttn[i]);
}
return 0;
}
Why???

var
a,b,c,d:array[0..100000] of longint;
n,m,i:longint;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]>x do
inc(i);
while x>a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
procedure sort2(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=b[(l+r) div 2];
repeat
while b[i]>x do
inc(i);
while x>b[j] do
dec(j);
if not(i>j) then
begin
y:=b[i];
b[i]:=b[j];
b[j]:=y;
y:=d[i];
d[i]:=d[j];
d[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort2(l,j);
if i<r then
sort2(i,r);
end;
procedure sort3(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=d[(l+r) div 2];
repeat
while d[i]<x do
inc(i);
while x<d[j] do
dec(j);
if not(i>j) then
begin
y:=d[i];
d[i]:=d[j];
d[j]:=y;
y:=c[i];
c[i]:=c[j];
c[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort3(l,j);
if i<r then
sort3(i,r);
end;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
for i:=1 to m do
begin
read(b[i]);
d[i]:=i;
end;
sort(1,n);
sort2(1,m);
for i:=1 to n do
inc(c[(i-1) mod m+1],a[i]);
sort3(1,m);
for i:=1 to m do
write(c[i],' ');
end.

估计我的方法最麻烦了。
第一次我WA了，因为我没有写sort3，
而是直接输出for i:=1 to m do write(c[d[i]])
后来发现有问题。
应先找到d[i]=1，输出c[i]
再找d[i]=2，。。。。。
所以干脆再排一遍。

提交一百次。。。

AC五十题，纪念

我这才是真正的幸运，没有超市；
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 2392 KiB, score = 1
测试数据 #1: Accepted, time = 0 ms, mem = 2388 KiB, score = 1
测试数据 #2: Accepted, time = 0 ms, mem = 2388 KiB, score = 1
测试数据 #3: Accepted, time = 0 ms, mem = 2388 KiB, score = 1
测试数据 #4: Accepted, time = 0 ms, mem = 2392 KiB, score = 1
测试数据 #5: Accepted, time = 0 ms, mem = 2388 KiB, score = 1
测试数据 #6: Accepted, time = 15 ms, mem = 2392 KiB, score = 1
测试数据 #7: Accepted, time = 58 ms, mem = 2392 KiB, score = 1
测试数据 #8: Accepted, time = 46 ms, mem = 2388 KiB, score = 1
测试数据 #9: Accepted, time = 46 ms, mem = 2392 KiB, score = 1
Accepted, time = 165 ms, mem = 2392 KiB, score = 10

program p1445;
type p=record
s:longint;
n:longint;
w:longint;
end;
var num,sum:longint;
a:array[1..100000]of longint;
b:array[1..100000]of p;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
procedure qsort1(l,r:longint);
var i,j,temp:longint;
begin
i:=l;
j:=r;
temp:=b[(i+j) div 2].w;
while i<=j do
begin
while b[i].w>temp do
inc(i);
while b[j].w<temp do
dec(j);
if i<=j then
begin
swap(b[i].w,b[j].w);
swap(b[i].s,b[j].s);
inc(i);
dec(j);
end;
end;
if l<j then
qsort1(l,j);
if i<r then
qsort1(i,r);
end;
procedure qsort3(l,r:longint);
var i,j,temp:longint;
begin
i:=l;
j:=r;
temp:=b[(i+j) div 2].s;
while i<=j do
begin
while b[i].s<temp do
inc(i);
while b[j].s>temp do
dec(j);
if i<=j then
begin
swap(b[i].w,b[j].w);
swap(b[i].s,b[j].s);
swap(b[i].n,b[j].n);
inc(i);
dec(j);
end;
end;
if l<j then
qsort3(l,j);
if i<r then
qsort3(i,r);

end;
procedure qsort2(l,r:longint);
var i,j,temp:longint;
begin
i:=l;
j:=r;
temp:=a[(i+j) div 2];
while i<=j do
begin
while a[i]>temp do
inc(i);
while a[j]<temp do
dec(j);
if i<=j then
begin
swap(a[i],a[j]);
inc(i);
dec(j);
end;
end;
if l<j then
qsort2(l,j);
if i<r then
qsort2(i,r);
end;
procedure calc;
var i,j:longint;
begin
for i:=1 to num do
begin
j:=i mod sum;
if j=0 then
j:=sum;
b[j].n:=b[j].n+a[i];
end;
end;
procedure getdata_and_init;
var i,j:longint;
begin
readln(num,sum);
for i:=1 to num do
read(a[i]);
readln;
for i:=1 to sum do
read(b[i].w);
readln;
for i:=1 to sum do
b[i].s:=i;
for i:=1 to sum do
b[i].n:=0;
end;
procedure output;
var i:longint;
begin
for i:=1 to sum-1 do
write(b[i].n,' ');
writeln(b[sum].n);
end;
begin
getdata_and_init;
qsort1(1,sum);
qsort2(1,num);
calc;
qsort3(1,sum);
output;
end.

编译通过...

├ 测试数据 01：答案正确... (0ms, 2144KB)

├ 测试数据 02：答案正确... (0ms, 2144KB)

├ 测试数据 03：答案正确... (0ms, 2144KB)

├ 测试数据 04：答案正确... (0ms, 2144KB)

├ 测试数据 05：答案正确... (0ms, 2144KB)

├ 测试数据 06：答案正确... (0ms, 2144KB)

├ 测试数据 07：答案正确... (0ms, 2144KB)

├ 测试数据 08：答案正确... (1864ms, 2144KB)

├ 测试数据 09：答案正确... (660ms, 2144KB)

├ 测试数据 10：答案正确... (12ms, 2144KB)

---|---|---|---|---|---|---|---|-

Accepted / 100 / 2537ms / 2144KB

很简单的方法却很有效，开了4个1..100000的数组……

type

arraytype=array [1..100000] of longint;

var

i,j,m,n:longint;

a,b,c,r:arraytype;

procedure qsort(l,h:longint;var x:arraytype;code:char);

//快排多个数组时用type定义，写两遍快排很占行数

//code是为了在排a的时候c一起更改而排b的时候不能改c

var

i,j,t,m:longint;

begin

i:=l;

j:=h;

m:=x[(i+j) div 2];

repeat

while x[i]>m do inc(i);

while m>x[j] do dec(j);

if ij;

if il then qsort(l,j,x,code);

end;

procedure apple;

var

i,j:longint;

begin

j:=1;

while jn then exit;

end;

end;

begin

readln(n,m);

for i:=1 to n do read(b[i]);

readln;

for i:=1 to m do read(a[i]);

readln;

for i:=1 to m do c[i]:=i;

fillchar(r,sizeof(r),0);

qsort(1,m,a,'a');

qsort(1,n,b,'b');

apple;

for i:=1 to m do

for j:=1 to m do

if c[j]=i then begin

write(r[j],' ');

break;

end;

end.

最后说一句，评测机抽的那么厉害我竟然1次AC没超时，rp+++++啊

我没有说完……陶陶的体重是无所谓的，但是陶陶的体重决定的编号是很有所谓的！！！

快排

回楼下下下下……的RAV同学，分明就是按题目的原序输出嘛，故意捣乱……

庆祝200个AC!!

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

就是快排

两次就好。。。

一次AC。

差点被水题虐了O.O

3*quick_sort

快排

"按原序输出"是废话废话废话废话废话废话废话废话废话废话废话废话废话废话！！！

就按体重从大到小输出！！！！！！！！！！！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 119ms

├ 测试数据 09：答案正确... 306ms

├ 测试数据 10：答案正确... 259ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：684ms

#include

using namespace std;

const int L=100001;

struct std

{

int num;

int weight;

int apple;

}t[L];

int size[L];

int N,M;

int comp1(const void *p1,const void p2)

{

return ((struct std *)p1).weight>(*(struct std *)p2).weight?-1:1;

}

int comp2(const void *p1,const void *p2)

{

return *(int *)p2>*(int *)p1?1:-1;

}

int comp3(const void *p1,const void p2)

{

return ((struct std *)p1).num>(*(struct std *)p2).num?1:-1;

}

void init(void)

{

int i;

cin>>N>>M;

for(i=1;i>size[i];

for(i=1;i>t[i].weight,t[i].num=i;

qsort(t+1,M,sizeof(t[0]),comp1);

qsort(size+1,N,sizeof(size[0]),comp2);

}

void work(void)

{

int i;

for(i=1;i

var i,j,k,n,m:longint;

a,b,f:array[1..100000] of longint;

u:array[1..100000,1..2] of longint;

procedure kp(l,r:longint);

var i,j,v:longint;

begin

if l

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

这题真水