pascal问题：智力大冲浪

贪心 pascal 智力大冲浪问题 贪心策略~

先按游戏罚钱多少排个序,然后从大到小一个一个的安排游戏,每个游戏尽可能往后安排.如果安排不了就只能放弃了.这样下来就是最优策略.

教师的细心解答，满意请采纳，谢谢

首先排序时用m替换会覆盖m原来的值，改成t
从前往后扫描，一旦a[i]>b[i]则move，下一次应该从i继续扫描，所以这里用for循环不好做，用while简单一些；我在程序上做了一些改动：
program zldcl;
var a,b,c:array[1..500] of integer;
m,n,i,j,x,s,t:integer;
f1,f2:text;
procedure move(s:integer); //
var i,j,g,h:integer;
begin
g:=c[1];
for i:=1 to s do
if c[i]<g then begin g:=c[i];h:=i;end;
m:=m-g;
for j:=h to n do begin b[j]:=b[j+1];c[j]:=c[j+1];end; //
dec(n); //
end;

begin
assign(f1,'in.txt');
reset(f1);
read(f1,m);read(f1,n);
for i:=1 to n do
begin
a[i]:=i;
read(f1,b[i]);
end;
for i:=1 to n do read(f1,c[i]);
close(f1);
s:=n;
for i:=1 to n-1 do
for j:=i to n do
if b[i]>=b[j] then
begin
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=c[i];c[i]:=c[j];c[j]:=t;
end;
//for i:=n downto 1 do if a[i]>b[i] then move;
i:=1; //
while i<n do //
begin //
if a[i]>b[i] then move(i) //
else inc(i); //
end; //
assign(f2,'out.txt');
rewrite(f2);
write(f2,m);
close(f2);

百度知道 > 电脑/网络 > 其他编程语言添加到搜藏待解决
pascal问题：智力大冲浪
悬赏分：80 - 离问题结束还有 5 天 20 小时
例2：智力大冲浪
小伟报名参加中央电视台的智力大冲浪节目。

本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者m元，先不要太高兴！因为这些钱还不一定就是你的，接下来主持人宣布了比赛规则。
首先，比赛时间分为n个时段（n<=500)，它又给出了很多小游戏，每个小游戏都必须在规定期限Ti前完成（1=<Ti<=n)。如果一个游戏没能在规定的期限前完成，则要从奖励费m元中扣去一部分钱Wi，Wi为自然数，不同的游戏扣去的钱是不一样的，当然，每个游戏本身都很简单，保证每个人都能在一个时段完成，而且都必须从整数段开始，主持人只是想考考参赛者如何安排组织自己做游戏的顺序，作为参赛者，小伟很想赢得冠军，当然更想赢取最多的钱，注意，比赛绝不让参赛者赔钱
[问题输入]
输入文件in.txt，共4行。
第1行为m，表示一开始奖励给每位参赛者的钱；
第2行为n，表示有n个小游戏；
第3行有n个数，分别表示游戏1到n的规定完成期限；
第4行有n个数，分别表示游戏1到n不能在规定期限前完成的扣款数。
[问题输出]
输出文件out.txt，仅1行。表示小伟能赢取最多的钱。
[输入样例]
10000
7
4 2 4 3 1 4 6
70 60 50 40 30 20 10
[输出样例]
9950

以下为本人所编程序，但运行出来结果不正确，请高手帮忙！谢谢 ！

program zldcl;
var a,b,c:array[1..500] of integer;
m,n,i,j,x,s:integer;
f1,f2:text;
procedure move;
var i,j,g,h:integer;
begin
g:=c[1];
for i:=1 to s do
if c[i]<g then begin g:=c[i];h:=i;end;
m:=m-g;
for j:=h to s do begin b[j]:=b[j+1];c[j]:=c[j+1];end;
s:=s-1;
end;

begin
assign(f1,'in.txt');
reset(f1);
read(f1,m);read(f1,n);
for i:=1 to n do
begin
a[i]:=i;
read(f1,b[i]);
end;
for i:=1 to n do read(f1,c[i]);
close(f1);
s:=n;
for i:=1 to n-1 do
for j:=i to n do
if b[i]>=b[j] then
begin
m:=b[i];b[i]:=b[j];b[j]:=m;
m:=c[i];c[i]:=c[j];c[j]:=m;
end;
for i:=n downto 1 do if a[i]>b[i] then move;
assign(f2,'out.txt');
rewrite(f2);
write(f2,m);
close(f2);

end.
问题补充：用贪心可以做
以下是分析：

因为不同的游戏不能准时完成具有不同的扣款数，而且是最优解问题，贪心
把所有数据按结束时间先后排序，然后从前向后扫描。
当扫描到第i时段，如果分配任务结束时间t[I]小于i,则说明
在前面这些游戏中必须舍弃一个，舍弃谁呢？
在1到i中选择一个扣款最小的去掉交累加扣款值
然后调整排列顺序，让后面的元素填补前面的空缺。

7

I 1 2 3 4 5 6 7
T[I] 4 2 4 3 1 4 6
B[I] 70 60 50 40 30 20 10
排列后
I 1 2 3 4 5 6 7
T[I] 1 2 3 4 4 4 6
B[I] 30 60 40 20 50 70 10
提问者： ￡东方￡ - 经理 四级

我来回答：

参考资料：
匿名回答 积分规则

回答 共 6 条
要用动态规划

我改完是这样的：
program zldcl;
var a,b,c:array[1..500] of integer;
m,n,i,j,x,s,t:integer;
f1,f2:text;
procedure move(s:integer);
var i,j,g,h:integer;
begin
g:=c[1];
for i:=1 to s do
if c[i]<g then begin g:=c[i];h:=i;end;
m:=m-g;
for j:=h to n do begin b[j]:=b[j+1];c[j]:=c[j+1];end;
dec(n);
end;

begin
assign(f1,'in.txt');
reset(f1);
read(f1,m);read(f1,n);
for i:=1 to n do
begin
a[i]:=i;
read(f1,b[i]);
end;
for i:=1 to n do read(f1,c[i]);
close(f1);
s:=n;
for i:=1 to n-1 do
for j:=i to n do
if b[i]>=b[j] then
begin
t:=b[i];b[i]:=b[j];b[j]:=t;
t:=c[i];c[i]:=c[j];c[j]:=t;
end;
i:=1;
while i<n do
begin
if a[i]>b[i] then move(i)
else inc(i);
end;
assign(f2,'out.txt');
rewrite(f2);
write(f2,m);
close(f2);
end.
应该是对的吧。

if c[i]<g then begin g:=c[i];h:=i;end;
这里有错误

典型贪心
陈题改编的

---

陕西省15279233496： Pascal 循环问题 - ？
元董甫美： 循环做法:枚举女生人数x,则男生人数为50-x 然后模拟女生进来,如果最后一个女生给9个男生礼物,则x是对的.数学做法:设女生人数为x,则男生人数为50-x 据题意,(50-x)-x=(9-1),所以x=21.所以女生有21个,男生有29个.

陕西省15279233496： pascal问题博弈论 - ？
元董甫美： 逆向考虑这个问题,一开始数字为s,A可以减a,B可以减B,减到0获胜.按照a、b、s的大小分类讨论 当s否则 a>b时,先手胜利.因为A一定可以先手将s变为s'使得s'恰好是a的K倍(K为整数),这样无论B怎样努力,A都可以保证在自己操作完...

陕西省15279233496： pascal 问题: 哪位高手能帮忙解决一下一个难题,将非常感谢. - ？
元董甫美： 明显可以看出用动态规划.我定义的数组h[i]...

陕西省15279233496： pascal题目!! - ？
元董甫美： var s,e,n,d,m,o,r,y,send,more,money:integer; begin for s:=1 to 9 do for e:=0 to 9 do...

陕西省15279233496： pascal 问题 - ？
元董甫美： 20a2,16进制.排除b,e,转成10进制是8354,排除a,c,所以第一个答案是d.2054,10进制,排除a,c,转成16进制,0806,排除b,e,所以答案还是d.

陕西省15279233496： 房间问题 Pascal 详解 急!？
元董甫美： USACO的房间问题? 用一个二维数组记录每个格的四面是否有墙,根据输入,利用位运算得出每个格的墙的情况(8 = 23,4 = 22,2 = 21,1 = 20). 然后用floodfill,对每个房间染色,求出房间数,和每个房间的面积,输出其中最大的. 枚举每堵...

陕西省15279233496： pascal题 - ？
元董甫美： var a:array [1..20] of integer; i,j,n:integer;begin randomize; for i:=1 to 20 do a[i]:=random(90)+10; for i:=1 to 20 do for j:=1 to 19 do if a[j]>a[j+1] then begin...

陕西省15279233496： Pascal问题 1031: 杨辉三角形？
元董甫美： var a:array[0..20,0..20] of longint; n,i,j:longint; begin readln(n); fillchar(a,sizeof(a),0); a[1,1]:=1; for i:=2 to n do for j:=1 to i do a[i,j]:=a[i-1,j]+a[i-1,j-1]; for i:=1 to n do begin write(a[i,1]); for j:=2 to i do write(' ',a[i,j]); writeln; end; readln; end.

陕西省15279233496： Pascal 练习!求解! - ？
元董甫美： 1a,x:longint;beginreadln(x);if x>50 then begina:=x-50;x:=50;end;writeln(x*0.35+a*0.5);end.2varx:longint;beginreadln(x);if x mod 3=2 thenif x mod 5=3 thenif x mod7=2 thenwriteln(...

陕西省15279233496： pascal约瑟夫问题 - ？
元董甫美： 给你更好理解的. 这是筛法 var n,m,i,s,p:integer; a:array[1..10000] of integer; begin read(n,m);//这步不用说了吧? for i:=1 to n do a[i]:=1;//先全部赋值1 p:=0;s:=0;//统计人数和报数字用的 repeat for i:=1 to n do begin if a[i]=0 then continue; //...