这超时超的,编译器都出不来了,求优化方案

P1478 陶陶摘苹果(升级版)

CCCCCreeper @ 2020-02-25 20:39:03

program p1478;
var x,y:array [1..5000] of integer;
n,s,a,b,i,j,app:integer;
begin
  readln(n,s);
  readln(a,b);
  for i:=1 to n do readln(x[i],y[i]);
  app:=0;
  while s>=0 do
  begin
    j:=1;
    for i:=2 to n do if y[i]<y[j] then j:=i;
    if (s-y[j]>=0)and(a+b>=x[i]) then
    begin
      s:=s-y[j];
      app:=app+1;
      y[j]:=32767;
    end;
  end;
  write(app);
end.

by Heap_Sort @ 2020-02-25 21:49:33

program p1478;
var x,y:array[0..5000] of integer;
n,s,a,b,i,j,app:integer;
begin
  readln(n,s);
  readln(a,b);
  for i:=1 to n do readln(x[i],y[i]);
  app:=0;
  y[0]:=32767;//保证能选到y[i]更小的
  while s>=0 do
  begin
    j:=0;//不能赋为1,当a+b<x[1]并且y[1]最小时就会出错
    for i:=1 to n do if(y[i]<y[j])and(a+b>=x[i])then j:=i;//选择最小值时就需要判断a+b是否大于x[i]。在后面判断,如果选到的够不到的话,就没办法找到最优解
    if s-y[j]>=0 then
    begin
      s:=s-y[j];
      app:=app+1;
      y[j]:=32767;
    end
    else break;//此时的力气连耗费最小的一个都摘不了,后面的更加摘不了,所以可以跳出循环
  end;
  write(app);
end.

by CCCCCreeper @ 2020-02-26 11:16:47

@ZZY729 感谢感谢


上一页 |