贪心与随机和法

1、http:/JudgeOnline/showproblem?problem_id=1060鹊桥相会Time Limit:1000MSMemory Limit:65536KTotal Submit:178 Accepted:37Description一年一度的七夕又要到了，可歌可泣的织女又可以在鹊桥相会了。不知道大家有没有雅兴陪redraiment 坐在葡萄藤下他们的。知道所以要与织女相见，必须要有喜鹊搭桥。必须在天河岸上等待，直到有喜鹊经过，于是可以搭乘这只喜鹊往河对岸走。当然，牛着去见织女，所有在途中，如果有速度更快的喜鹊赶上了他，他就会换乘那只速度更快的喜鹊。可以假定喜鹊的速度是恒定不变的

2、，并且喜鹊一直是沿直线飞行的(不转弯，更不回头)，坐上喜鹊所花的时间忽略不计。现给出天河的宽度、每只喜鹊的初始位置(所在位置为 0，天河方向为设正方向)以及它们的速度(有可能是负数，代表喜鹊往反方向飞行)，这些数据都是整数。请你来帮忙计算一下早些有终成眷属。_到达对岸与织女相会最少需要多少时间，让他们当然，如果没有喜鹊来搭载，的就到不了对岸与织女相会了，祈祷不要发生这样的事情。只好很遗憾的跟说：“Cant Solve”，那Input第一行有两个数据w、n，分别代表天河的宽度( 1n10000)。:km)和喜鹊的只数(1w1000,接下来从第二行到第n+1 行每行都有两个数据 t、v，分别代表

3、1 只喜鹊的初始位置(:m)和它的飞行速度(:m/s)(-1000t1000, -100v100)。所有的数据范围都不会超过 32 位整数的表示范围(用型数据不会溢出)。输入以 0 0 结束。Output如果能到达对岸输出他到达对岸所花的总时间(结果精确到秒即可，小数部分舍去)；否则输出“Cant Solve”。Sle Input100110Sle Output1000varmin,i,w,n,t,v:long; beginreadln(w,n); while(w0)or(n0) dobeginmin:=maxlong; for i:=1 to n dobeginreadln(t,v); if

4、(t0)and(w*1000-t)div then min:=(w*1000-t)div v;end;vmin)if mthen elseaxlongwriwrin(min)n(Cant Solve);readln(w,n);end;end.ht/Problem_Show.as=10972004T 合并果子（fruit.pas/dpr/p）【问题描述】在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子一堆。每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 n-1 次合并之后，就只剩下一堆了。多

5、多在合并果子时总共消耗的体力等于每次合并所消耗体力之和。因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。例3 种果子，数目依次为 1，2，9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明 15 为最小的体力耗费值。【输入文件】输入文件fruit.in 包括两行，第一行是一个整数 n(1=n

6、=10000),表示果子的种类数。第二行包含n 个整数，用空格分隔，第i 个 ai(1=ai=20000)是第 i 个果子的数目。【输出文件】输出文件 fruit.out 包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于 231。【样例输入】31 2 9【样例输出】15【数据规模】对于 30%的数据，保证有 n=1000;对于 50%的数据，保证有 n=5000;对于全部的数据，保证有 n=10000。【入门】买蛋糕 II时间限制：1000MS内存限制：1000K解答次数：51 通过次数：11【试题描述】今天是路路的生日，生日蛋糕自然是少不了。路路的朋友们一起去蛋

7、糕店来买蛋糕，等一行人到了蛋糕店之后，发现那里是人山人海啊-_-。这下可把店家给急坏了，因为人数过多，需求过大，所以人们要等好长时间才能拿到自己的蛋糕。为了最大限度的使每位客人尽快拿到蛋糕，因此他需要安排一个制作顺序，使每位客人的平均等待时间最少（如果制作时间相同的，先来的先做）。这使他发愁了，于是他请你来帮忙安排一个制作顺序，使得每位客人的平均等待时间最少。【输入描述】输入有两行。第一行是一个整数 n，表示有 n 种蛋糕等待制作。第二行有 n 个数，第i 个数表示第 i 种蛋糕的制作时间。【输出描述】输出包括一行，有 n 个整数，每 2 个整数间用空格隔开，是蛋糕的制作顺序，每个数即是蛋糕的

8、。【输入样例】21 2【输出样例】1 2【解题提示】对于 100%的数据，n = 1000。htt:8080/BS41Online/showproblem?problem_id=1002【培训试题】排队打水问题(normal)Time Limit:1000MSMemory Limit:65536KTotal Submit:934 Accepted:325Description有n 个人排队到 r 个水龙头去打水，他们装满水桶的时间t1、t2tn 为整数且各不相等，应如何安排他们的打水顺序才能使他们总共花费的时间最少？Input第一行n，r (n=500,r=75)第二行为n 个人打水所用的时间

9、Ti (Tiajthen begemp:=ai;ai:=aj;aj:=temp;end;for i:=1 to rdobeginj:=i;s:=0;while j=n dobegins:=s+aj;bj:=s;j:=j+r;end;end;s:=0;for i:=1 ton dos:=s+bi;wrin(s);end.5Mixing Milk 混合牛奶描述牛奶包装是一个如此低利润的生意,所以尽可能低的控制初级产品(牛奶)的价格变的十分重要。请帮助 Marry 的牛奶制造公司(Merry Milk Makers)以可能的最廉价的方式取得他们所需的牛奶。Marry 的牛奶制造公司从一些农民那牛奶，

10、每个农民卖给牛奶制造公司的价格不一定相同。而且,如一只母牛一天只能生产一定量的牛奶,农民每一天只有一定量的牛奶可以卖。每天,Marry 的牛奶制造公司从每个农民那出 Marry 牛奶制造公司的一定量的牛奶,少于或等于农民所能提供的最大值。给的牛奶需求,连同每个农民的可提供的牛奶量和每的价格,请计算 Marry 的牛奶制造公司所要付出钱的最小值。注意:每天农民生产的牛奶的总数对 Marry 的牛奶制造公司来说足够的。格式PROGRAM NAME: milkINPUT FORMAT:(file milk.in)第 1 行:二个整数,N 和 M。第一个数值,N,(0=数量。N=2,000,000)是

11、 Marry 的牛奶制造公司的一天需要牛奶的第二个数值,M,(0=M=5,000)是提供牛奶的农民个数。第 2 到 M+1 行:每行二个整数,Pi 和 Ai。Pi(0= Pi=1,000) 是农民 i 牛奶的价格。Ai(0 = Ai = 2,000,000)是农民 i 一天能卖给 Marry 的牛奶制造公司的牛奶数量。OUTPUT FORMAT:(file milk.out)单独的一行包含单独的一个整数，表示 Marry 的牛奶制造公司拿到所需的牛奶所要的最小费用SLE INPUT100 5593862040108030SLE OUTPUT630代码：ID:jzkkwei1 PROG: mil

12、k LANG: PASCALprogram milk; varcost:64;i,j,temp,n,m:long p:array1.5000of a:array1.5000of;long long;procedure varc:long beginc:=a;a:=b;b:=c; end; procedure varswap(var a,b:long);sort(lx,rx:long);i,j,x:long; begini:=lx;j:=rx; x:=prandom(j-i+1)+i; repeatwhile (pix)dec(j);dodoif ij;if ilx then sort(lx,j

13、);end; beginrandomize; assign(input,milk.in);reset(input); assign(output,milk.out);rewrite(output); readln(n,m);for i:= 1 to m doreadln(pi,ai);sort(1,m);i:=1;cost:=0; while n0 dobeginif ai=0 then inc(i); if n-ai=0 thenbeginn:=n-ai;temp:=ai*pi;ai:=0;endelsebegintemp:=n*pi; n:=0;end; cost:=cost+temp;e

14、nd; n(cost);wriclose(input); close(output);end.ht排座椅1 排座椅/Problem_Show.as=1498（seat.pas/【问题描述】p）上课的时候总有一些同学和前后左右的人交头接耳，这是令小学班十分头疼的一件事情。不过，班的 D 对同学上小雪发现了一些有趣的现象，当的座次确定下来之后，只有有限会交头接耳。在教室中坐成了 M 行N 列，坐在第 i 行第 j 列的同学的位置是（i，j），为了方便进出，在教室中设置了 K 条横向的通道，L 条纵向的通道。于是，聪明的小雪想到了一个办法，或以减少上学生交头接耳：她打算重新摆放桌椅，改变桌椅间通道的

15、位置，因为如果一条通道隔开了两个会交头接耳的同学，那么他们就不会交头接耳了。请你帮忙给小雪编写一个程序，给出最好的通道划分方案。在该方案下，上的学生对数最少。交头接耳【输入】输入文件 seat.in 的第一行，有 5 各用空格隔开的整数，分别是M，N，K，L，D（2=N， M=1000，0=KM，0=LN，D=2000）。接下来 D 行，每行有 4 个用空格隔开的整数，第i 行的 4 个整数 Xi，Yi，Pi，Qi，表示坐在位置(Xi,Yi)与(Pi,Qi)的两个同学会交头接耳（输入保证他们前后相邻或者左右相邻）。输入数据保证最优方案的唯一性。【输出】输出文件 seat.out 共两行。第一行

16、包含 K 个整数，a1a2aK，表示第 a1 行和 a1+1 行之间、第 a2 行和第 a2+1 行之间、第 aK 行和第aK+1 行之间要开辟通道，其中 ai ai+1，每两个整数之间用空格隔开（行尾没有空格）。第二行包含L 个整数，b1b2bk，表示第 b1 列和 b1+1 列之间、第 b2 列和第 b2+1 列之间、第 bL 列和第bL+1 列之间要开辟通道，其中 bix2then inc(ax2) else inc(ax1)elseif x1=x2 thenif y1y2then inc(by2) else inc(by1);end;fillchar(ar,sizeof(ar),0); for i:=1 to k dobeginmax:=1;for j:=2 to m do if ajamax then max:=j;amax:=0;inc(ar0);arar0:=max; end;for i:=1 to ar0-1 do for j:=i+1 to ar0 doif ariarj thenbeg:=ari;ari:=arj;arj:=t;end;for i:=1 to ar0-1 do write(ari, );wrin(arar0);fill