Attention!

个人在调试的时候发现，用快排是有漏洞的

比如如下的数据：

3 1 3

100

100

100

正确答案显然是 100

但是，因为快排的不稳定性，很容易造成错解输出0。就上面的数据而言，我们要找的最优坐标是(1,1)(2,1)(3,1)三者之一，只有选(1,1)是可行的。但排序后或许我们选的第一个坐标就换成了(2,1)或(3,1),这时多多不可能在第一次采摘后返回路边，所以程序输出错误的0。

由于数据巨水，所以很多人忽略上面这点就可以AC，但是理论上是不可行的

如果想要完美地solve此题 那么

解决的办法有：

1、换用归并、插入、冒泡等稳定的排序方法；

2、在快排里加条件语句规避不稳定情况；

3、不用排序，每次枚举最大值。

关于第3点，因为枚举的顺序是服从(X, )的升序排列的，只有value

刚开始输错了一个变量，没想到还过了8个点，rp高

{y[p]:=((i-x[p]) div m!!!)+1;}

type l=array[0..1000] of longint;

var a,x,y:l;

s,m,n,k,i,j,g,t,total,p,temp:longint;

begin

readln(m,n,k); p:=0; t:=0; total:=0;

fillchar(a,sizeof(a),0); a[0]:=-maxlongint; a[1]:=maxlongint;

fillchar(x,sizeof(x),0);

fillchar(y,sizeof(y),0);

for i:=1 to m*n do

begin

read(s);

if s0 then begin inc(p); a[p]:=s; x[p]:=i mod n; if x[p]=0 then x[p]:=n; y[p]:=((i-x[p]) div n)+1; end;

end;

for i:=1 to p-1 do

begin

g:=i;

for j:=i+1 to p do

if a[g]>a[j] then g:=j;

temp:=a[i]; a[i]:=a[g]; a[g]:=temp;

temp:=x[i]; x[i]:=x[g]; x[g]:=temp;

temp:=y[i]; y[i]:=y[g]; y[g]:=temp;

end;

x[p+1]:=x[p]; y[p+1]:=1;

for i:=p downto 1 do

if t+abs(x-x[i])+abs(y-y[i])+y[i]>k-2 then break

else begin

inc(total,a[i]);

inc(t,abs(x-x[i])+abs(y-y[i])+1);

end;

writeln(total);

end.

{

ID:p.tiany1

PROG:1120

LANG:PASCAL

}

program p1120;

type

arr=record

i,j,val:longint;

end;

var

a:Array[0..1000] of arr;

n,m,k,p:longint;

procedure init;

var

i,j,l:longint;

begin

readln(n,m,k);

p:=0;

for i:=1 to n do

for j:=1 to m do

begin

read(l);

if l0 then

begin

inc(p);

a[p].i:=i;

a[p].j:=j;

a[p].val:=l;;

end;

end;

end;

procedure qsort(s,l:longint) ;

var

i,j,x:longint;

begin

i:=s;j:=l;

x:=a[(i+j) div 2].val;

repeat

while a[i].val>x do inc(i);

while a[j].valk) then begin writeln(0);exit;end;

x:=a[1].i;

y:=a[1].j;

sum:=a[1].val;

t:=a[1].i+1;

for i:=2 to p do

begin

t1:=t+abs(a[i].i-x)+abs(a[i].j-y)+a[i].i+1;

if t1

哈哈，随随便便就做出一题。。。哎！！

var m,n,k,max,max1,max2,maxi1,maxi2,i,j,t,s:longint;

a:array[0..30,0..30] of longint;

begin

readln(m,n,k);

k:=k-2;

max:=0;

for i:=1 to m do

for j:=1 to n do

begin

read(a);

if a>max then begin max:=a; max1:=i; max2:=j; end;

end;

t:=max1; s:=0;

while (t+max1-10) do

begin

a[max1,max2]:=0;

s:=s+max;

max:=0;

for i:=1 to m do

for j:=1 to n do

if a>max then begin max:=a; maxi1:=i; maxi2:=j; end;

t:=t+1+abs(maxi1-max1)+abs(maxi2-max2);

max1:=maxi1; max2:=maxi2;

end;

writeln(s);

end.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

#include

main()

{

int M,N,K,u[20][20],p[4000],ans1=0,ans2=0;

int i,j,y,t,a,b,c=0;

scanf("%d%d%d",&M,&N,&K);

y=0;

for(i=0;i

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

a:array[1..20,1..20]of longint;

p:array[1..400,0..2]of longint;

m,n,k,total:longint;

procedure swap(var a,b:longint);

var

t:longint;

begin

t:=a;

a:=b;

b:=t;

end;

procedure init;

var

i,j,s:longint;

begin

readln(m,n,k);

s:=0;

for i:=1 to m do

begin

for j:=1 to n do

begin

read(a);

inc(s);

p:=a;

p:=i;

p:=j;

if p>0 then inc(total);

end;

readln;

end;

for i:=1 to m*n-1 do

for j:=i+1 to m*n do

if pk then break;

t:=t+d;

s:=s+p;

x:=p;

y:=p;

end;

writeln(s);

end;

begin

init;

main;

end.

一次ac，ye！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

var

a:array[1..20,1..20]of integer;

m,n,k,i,j,max,x,y,x1,y1:integer;

ans:longint;

begin

ans:=0;

readln(m,n,k);

for i:=1 to m do

for j:=1 to n do

read(a);

for i:=1 to m do

for j:=1 to n do

if a>max then

begin

max:=a;

x1:=i;

y1:=j;

end;

x:=0;

y:=y1;

k:=k-abs(x-x1)-abs(y-y1)-1;

while k>=x1 do

begin

ans:=ans+max;

a[x1,y1]:=0;

x:=x1;

y:=y1;

max:=0;

for i:=1 to m do

for j:=1 to n do

if a>max then

begin

max:=a;

x1:=i;

y1:=j;

end;

k:=k-abs(x-x1)-abs(y-y1)-1;

end;

writeln(ans);

end.

Flag 　　 Accepted

题号 　　P1120

类型(?) 　　贪心

通过 　　2356人

提交 　　5999次

通过率 　　39%

难度 　　2

提交 讨论 题解

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

program p1120(input,output);

var

a:array[1..20,1..20]of integer;

m,n,k,i,j,max,x,y,x1,y1:integer;

ans:longint;

begin

ans:=0;

readln(m,n,k);

for i:=1 to m do

for j:=1 to n do

read(a);

for i:=1 to m do

for j:=1 to n do

if a>max

then begin max:=a;x1:=i;y1:=j;end;

x:=0;

y:=y1;

k:=k-abs(x-x1)-abs(y-y1)-1;

while k>=x1 do

begin

ans:=ans+max;

a[x1,y1]:=0;

x:=x1;

y:=y1;

max:=0;

for i:=1 to m do

for j:=1 to n do

if a>max

then begin max:=a;x1:=i;y1:=j;end;

k:=k-abs(x-x1)-abs(y-y1)-1;

end;

writeln(ans);

end.

居然要完全按照顺序采！……

不满足就退出

这害死多少人啊……

这个题目并不难，但有很多地方需要注意，比如摘花生也需要时间，题解描述也很混乱，比如最后跳到路上还是第一行。

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

交了N次才AC

program vijos_1120;

const

maxN=50;

maxNNuts=maxN*maxN;

type

TNut=record

w,x,y:longint

end;

var

n,m,k,ans:longint;

NNuts:longint;

nuts:array[1..maxNNuts] of TNut;

procedure init;

var

i,j,t:longint;

begin

readln(n,m,k);

NNuts:=0;

for i:=1 to n do begin

for j:=1 to m do begin

read(t);

if t>0 then begin

inc(NNuts);

with nuts[NNuts] do begin

w:=t;

x:=i;

y:=j;

end;

end;

end;

readln;

end;

end;

var

temp:TNut;

procedure qsort(l,r:longint);

var

i,j,x:longint;

begin

i:=l; j:=r; x:=nuts[(i+j)>>1].w;

repeat

while nuts[i].w>x do inc(i);

while nuts[j].w

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

I'm NO.2300 ^_^

program p1120;

var s:array[1..20,1..20]of integer;

n,m,y,x,k,t,b,n1,m1,n2,m2,q:integer;

procedure cz;

begin

for y:=1 to m do

for x:=1 to n do

begin

if s[y,x]>=b then

begin

b:=s[y,x];

begin

if n1>x then

n2:=n1-x

else

n2:=x-n1;

if m2>y then

m2:=m1-y

else

m2:=y-m1;

end;

n1:=x;

m1:=y;

s[y,x]:=0;

end;

end;

end;

begin

readln(n,m,t);

for y:=1 to m do

begin

begin

for x:=1 to n do

read(s[y,x]);

end;

readln;

end;

cz;

if b=0 then

write(0)

else

begin

begin

t:=t-y;

while t

我就纳死闷了？？？ 为什么会有错误103呢？？？？？？

MD WA了20次！！！ 卧槽！！！！！ 哥哥的AC率都被VIJOS坑没了！！

还有 veryguo614 你个小屁孩，你TMD的20分的程序瞎晒个啥？？

MD哥哥照你程序改过来改过去 浪费哥哥我一上午的时间！！！！

你小子很不地道啊！！

哎，太简单了，一次就AC，反正贪心+快排

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

水题WA4次……前两次把坐标打错居然有60分……（数据弱死了）

第三次想多了，举个例子

1 10 6

1 0 0 0 0 0 0 0 0 1

我以为输出的是2

步骤：

1、从路上跳到(1,1)

2、摘花生

3、跳回路上

4、从路上跳到(1,10)

5、摘花生

6、回到路上

其实输出的是1，跳到路上就不能回去花生田了……

第四次莫名其妙说我第7点超时

第五次提交MS……

水到死..........还想复杂了，其实就一模拟..........

考察排序，以及模拟算法设计。

算法：

1. 读入数据，记录有效数据，即有花生的点以及点的花生数。可以用记录储存或者多用几个数组。推荐数组！编写方便。不过用记录更清晰。

2. 对花生数进行从大到小排序。选排、快排均可。不过考虑到数据不大，没必要用快排。看你爱好。

3. 按花生数顺序进行逐个处理。注意区分①评价可否摘到并退出②实行采摘

步骤：①算 移动+采摘+回路边 的时间

②判断是否满足总时间限制limit

若满足则实行采摘，nowt:=nowt+移动到该点+1；并统计花生数。

若不满足，则由上一点退出花生田。

4. 输出总数