八十中学科技夏令营课程[一]算法训练.pptVIP

八十中学信息奥赛教练 贾志勇 算法训练 北京市第八十中学雏鹰建言体验营信息技术课程[一] 例题1：排队打水 有N个人排队到R个水龙头去打水，他们装满水桶的时间T1，T2，……，Tn为整数且各不相同，应如何安排他们的打水顺序才能使他们花费的时间最少？ [问题描述]设有n个正整数，将他们连接成一排，组成一个最大的多位整数。例如:n=3时，3个整数13,312,343,连成的最大整数为又如:n=4时,4个整数7,13,4,246连接成的最大整数为7424613 输入：N N个数 输出:连接成的多位数 例题２：连成的多位数 　键盘输入一个高精度的正整数N（此整数中没有‘0’），去掉其中任意S个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的N和S，寻找一种方案使得剩下的数字组成的新数最小。 　　输出应包括所去掉的数字的位置和组成的新的正整数。（N不超过240位） 　　输入数据均不需判错。 【输入】 n s 【输出】 最后剩下的最小数。 【样例输入】 175438 4 【样例输出】 13 例题３：删数问题 考核1：编码问题 设有一个数组A:ARRAY[0..N-1] OF INTEGER；数组中存放的元素为0～N-1之间的整数，且A[i]≠A[j]（当i≠j时）。例如：N=6时，有： A=（4，3，0，5，1，2）此时，数组A的编码定义如下：A[0]的编码为0；A[i]的编码为：在A[0]，A[1]，…，A[i-1]中比A[i]的值小的个数（i=1，2，…，N-1）∴ 上面数组A的编码为： B=（0，0，0，3，1，2）程序要求解决以下问题：① 给出数组A后，求出其编码。② 给出数组A的编码后，求出A中的原数据 考核２：均分纸牌 [问题描述]　　有 N 堆纸牌，编号分别为 1，2，…, N。每堆上有若干张，但纸牌总数必为 N 的倍数。可以在任一堆上取若于张纸牌，然后移动。　　移牌规则为：在编号为 1 堆上取的纸牌，只能移到编号为 2 的堆上；在编号为 N 的堆上取的纸牌，只能移到编号为 N-1 的堆上；其他堆上取的纸牌，可以移到相邻左边或右边的堆上。　　现在要求找出一种移动方法，用最少的移动次数使每堆上纸牌数都一样多。　　例如 N=4，4 堆纸牌数分别为：　　①　9　②　8　③　17　④　6　　移动3次可达到目的：　　从 ③ 取 4 张牌放到 ④ （9 8 13 10） - 从 ③ 取 3 张牌放到 ②（9 11 10 10）- 从 ② 取 1 张牌放到①（10 10 10 10）。 [输 入]：　　键盘输入文件名。文件格式：　　N（N 堆纸牌，1 = N = 100）　　A1 A2 … An （N 堆纸牌，每堆纸牌初始数，l= Ai =10000） [输 出]：　　输出至屏幕。格式为：　　所有堆均达到相等时的最少移动次数。‘ 思考题 了解一下快速幂，这是倍增思想