临终之梦 - 2008/7/16 9:44:00
program mouse;
var
a,d:array[1..1500,1..1500]of longint;
b,c:array[1..1000]of longint;
n,i,t,max,j,m,q:longint;
begin
readln(n);
for i:=1 to n do
read(b);
readln;
for i:=1 to n do
read(c);
{for i:=1 to n-1 do
for j:=i+1 to n do
if b>b[j] then
begin
t:=b;
b:=b[j];
b[j]:=t;
t:=c;
c:=c[j];
c[j]:=t;
end;}
for i:=1 to n do
begin
a[b,c]:=c;
d[b,c]:=d[b,c]+1;
end;
i:=0;
while i<n do
begin
i:=i+1;
t:=i;
m:=0;
for j:=100 downto 1 do
if d[i,j]>=1 then
begin
q:=j;
break;
end;
while t>0 do
begin
if d[i,j]>=1 then
begin
m:=m+a[i,j];
t:=t-1;
d[i,j]:=d[i,j]-1;
end
else j:=j-1;
end;
if m>=(max+a[i,q])
then max:=m
else max:=max+a[i,q];
end;
writeln(max);
end.
为啥会溢出？
PS：我承认这题本身做法就不一定对
PS2:这年头貌似PASCAL只有初中高中的竞赛用用了
粘土火星 - 2008/7/16 10:04:00
[strike]for j:=100 downto 1
这是啥？
PS：变量名好囧，等下仔细看看……[/strike]
试验了一下……根本编译不了=v=b
很好奇你怎么能出现over range的问题，TP只有too large，囧
你搞了2个longint大数组 1500*1500*4byte*2/1024=17578k，TP静态数据空间只有64k，怎么能装得下。。。
如果用的是FP或者DELPHI = =，检查后面的语法错误吧，囧
临终之梦 - 2008/7/16 10:10:00
是 for j:=100 downto 1 do 的说
粘土火星 - 2008/7/16 10:38:00
什么题=v=？
临终之梦 - 2008/7/16 10:55:00
地鼠游戏（mouse.pas/in/out）
王钢是一名学习成绩优异的学生，在平时的学习中，他总能利用一切时间认真高效地学习，他不但学习刻苦，而且善于经常总结、完善自己的学习方法，所以他总能在每次考试中得到优异的分数，这一切很大程度上是由于他是一个追求效率的人。
但王钢也是一个喜欢玩的人，平时在学校学习他努力克制自己玩，可在星期天他却会抽一定的时间让自己玩一下，他的爸爸妈妈也比较信任他的学习能力和学习习惯，所以在星期天也不会象其他家长一样对他抓紧，而是允许他在星期天上午可以自由支配时间。
地鼠游戏是一项需要反应速度和敏捷判断力的游戏。游戏开始时，会在地板上一下子冒出很多地鼠来，然后等你用榔头去敲击这些地鼠，每个地鼠被敲击后，将会增加相应的游戏分值。问题是这些地鼠不会傻傻地等你去敲击，它总会在冒出一会时间后又钻到地板下面去（而且再也不上来），每个地鼠冒出后停留的时间可能是不同的，而且每个地鼠被敲击后增加的游戏分值也可能是不同，为了胜出，游戏参与者就必须根据每个地鼠的特性，有选择地尽快敲击一些地鼠，使得总的得分最大。
这个极具挑战性的游戏王钢特别喜欢，最近他经常在星期天上午玩这个游戏，慢慢地他不但敲击速度越来越快（敲击每个地鼠所需要的耗时是1秒），而且他还发现了游戏的一些特征，那就是每次游戏重新开始后，某个地鼠冒出来后停留的时间都是固定的，而且他记录了每个地鼠被敲击后将会增加的分值。于是，他在每次游戏开始后总能有次序地选择敲击不同的地鼠，保证每次得到最大的总分值。
输入输出要求:
输入文件mouse.in包含3行，第一行包含一个整数n（1<=n<=100）表示有n个地鼠从地上冒出来，第二行n个用空格分隔的整数表示每个地鼠冒出后停留的时间，第三行n个用空格分隔的整数表示每个地鼠被敲击后会增加的分值（<=100）。每行中第i个数都表示第i个地鼠的信息。
输出文件mouse.out只有一行一个整数，表示王钢所能获得的最大游戏总分值。
样例:
mouse.in
5
5 3 6 1 4
7 9 2 1 5
mouse.out
24
你直接给我标程也可以-_-b
Prz - 2008/7/16 11:22:00
er... 楼主最好养成好习惯，用稍微有说明性的变量名。多敲两个字用不了多少时间，而且会降低差错的时间，特别是让别人帮你找错的时候(竞赛里面不少这种情况，俗话说不识庐山真面目...)。
存取一个数组的元素要加索引的吧，光 b c 没有意义...
d[b,c]:=d[b,c]+1; <--- 数据都没有初始化，没有意义+1还是等于没有意义
临终之梦 - 2008/7/16 11:29:00
原帖由 Prz 于 2008-7-16 11:22:00 发表
没有意义+1还是等于没有意义 |
这话好经典-_-b
Prz - 2008/7/16 11:30:00
嗯，另外，顶楼的算法好像是一种贪婪算法，那么应该是错的。
这道题不能用贪婪算法。
临终之梦 - 2008/7/16 11:31:00
原帖由 粘土火星 于 2008-7-16 10:04:00 发表
[strike]for j:=100 downto 1
这是啥？
PS：变量名好囧，等下仔细看看……[/strike]
试验了一下……根本编译不了=v=b
很好奇你怎么能出现over range的问题，TP只有too large，囧
你搞了2个longint大数组 1500*1500*4byte*2/1024=17578k，TP静态数据空间只有64k，怎么能装得下。 |
我用的FP,试着把longint改成integer了,还是不行
话说我原来开的是两个100*100的数组的说
临终之梦 - 2008/7/16 11:32:00
原帖由 Prz 于 2008-7-16 11:30:00 发表
嗯，另外，顶楼的算法好像是一种贪婪算法，那么应该是错的。
这道题不能用贪婪算法。 |
所以我一开始就没说这算法是对的啊-_-b
只是想知道那里出问题了
Prz - 2008/7/16 11:39:00
算法错误，就算改掉了实现的错误，还是没有用处啊....
我看多半在没有初始化数据上，太多的东西都没有初始化||||||||||||
那个max也是，什么值都不知道就开始比较，最后结果还是没有意义。
只要有一个没有意义的数据都可能造成溢出，那个程序里面有几百万个.....
粘土火星 - 2008/7/16 11:53:00
原帖由 Prz 于 2008-7-16 11:30:00 发表
嗯，另外，顶楼的算法好像是一种贪婪算法，那么应该是错的。
这道题不能用贪婪算法。 |
这个题能用的嘛，叙述里说的是“一下子”全冒出来……排一下序然后贪就可以了
PS：LZ为啥把排序注释掉了……囧
PS2：你用FP那两个数组定义是没问题的，问题在于你read时候没写下标等等等……
Prz - 2008/7/16 11:57:00
贪婪不一定能达到最佳值。
例1，一下子出现2支: 第一支1分停1秒，第二只10分停2秒；
例2，一下子出现3支: 第一支1分停1秒，第二、三只各10分停2秒。
贪婪算法的话这两个例子总有一个达不到最佳。
------------
哦，貌似我想复杂了，排序以后倒过来选应该可以贪婪。=v=
------------
至于下标，好像都是缺少i，难道是这个论坛屏蔽了一些字符？
果然
被当成UBB处理了... ||||||||||||||
以后贴代码记得用
标签哦
粘土火星 - 2008/7/16 12:12:00
原帖由 Prz 于 2008-7-16 11:57:00 发表
贪婪不一定能达到最佳值。
例1，一下子出现2支: 第一支1分停1秒，第二只10分停2秒；
例2，一下子出现3支: 第一支1分停1秒，第二、三只各10分停2秒。
贪婪算法的话这两个例子总有一个达不到最佳。 |
囧，那贪得也太纯了……
这两种情况最纯的是……………………把所有鼠的积分加起来就是解……囧
粘土火星 - 2008/7/16 12:16:00
原帖由 Prz 于 2008-7-16 12:14:00 发表
er... 第二种情况不能加...时间不够的 |
orz……眼花了
我看成第一只停1分1秒……第二只停10分2秒……囧
临终之梦 - 2008/7/16 12:45:00
不觉得这贴只有我们三儿在理睬么
临终之梦 - 2008/7/16 12:46:00
有兴趣的话做做这道吧:
五、火车线路(rai.pas)
（本题不作为模拟竞赛题，作为模拟赛后练习偏难题用，训练得部份分）
某列火车行使在C个城市之间(出发的城市编号为1，结束达到的城市的编号为C)，假设该列火车有S个座位，现在有R笔预订票的业务。现在想对这R笔业务进行处理，看哪些预定能满足，哪些不能满足。
一笔预定由O、D、N三个整数组成，表示从起点站O到目标站D需要预定N个座位。一笔预定能满足是指该笔业务在行程范围内有能满足的空座位，否则就不能满足。一笔业务不能拆分，也就是起点和终点站不能更改，预定的座位数目也不能更改。所有的预定需求按给出先后顺序进行处理。
请你编写程序，看那些预定业务能满足，那些不能满足。
输入：
输入文件中的第一行为三个整数C、S、R，(1<=c<=60 000, 1<=s<=60 000, 1<=r<=60 000)他们之间用空隔分开。接下来的R行每行为三个整数O、D、N，(1<=o<d<=c, 1<=n<=s)，分别表示每一笔预定业务。
输出：
对第I笔业务，如果能满足，则在输出文件中的第I行输出“T”，否则输出“N”
示例：
Rai.in
4 6 4
1 4 2
1 3 2
2 4 3
1 2 3
Rai.out
T
T
N
N
Prz - 2008/7/16 13:11:00
这道题好像目标定义不清吧，都不知道要干什么。我随便选一下也是正确答案么？
总要要求满足尽可能多的业务数目，或者使得空座位尽可能少吧
粘土火星 - 2008/7/16 14:06:00
原帖由 Prz 于 2008-7-16 13:11:00 发表
这道题好像目标定义不清吧，都不知道要干什么。我随便选一下也是正确答案么？
总要要求满足尽可能多的业务数目，或者使得空座位尽可能少吧 |
囧，也许还要加一条线路尽可能长