分类： Code

问题描述
　　N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。
输入格式
　　第一行两个正整数N M 接下来一行N个正整数Ti。
　　N,M<=1000，Ti<=1000
输出格式
　　最小的等待时间之和。（不需要输出具体的安排方案）
样例输入
7 3
3 6 1 4 2 5 7
样例输出
11
提示
　　一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。
　　例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。
　　第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6
　　第二个龙头打水的人总等待时间 = 0 + 2 = 2
　　第三个龙头打水的人总等待时间 = 0 + 3 = 3
　　所以总的等待时间 = 6 + 2 + 3 = 11

 

问题描述
　　将1，2，…，9共9个数分成三组，分别组成三个三位数，且使这三个三位数构成
　　1：2：3的比例，试求出所有满足条件的三个三位数。
　　例如：三个三位数192，384，576满足以上条件。
输入格式
　　无输入文件
输出格式
　　输出每行有三个数，为满足题设三位数。各行为满足要求的不同解。
分析：先确定第一个数字，然后判断这个数字的两倍数和三倍数是否满足条件~用book数组标记当前数字是否已经出现过~

 

求最短路径最常用的算法有：
Dijkstra算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法。
Dijkstra算法、SPFA算法、Bellman-Ford算法这三个求单源最短路径，最后一个Floyd-Warshall算法可以求全局最短路径也可以求单源路径，效率比较低。
SPFA算法是Bellman算法的队列优化。
Dijkstra算法不能求带负权边的最短路径，而SPFA算法、Bellman-Ford算法、Floyd-Warshall可以求带负权边的最短路径。
Bellman-Ford算法的核心代码只有4行，Floyd-Warshall算法的核心代码只有5行。

1.最基本的求单源最短路径方法是图的深度优先遍历：
用 min = 99999999 记录路径的最小值，book[i]标记结点 i 是否被访问过~

2.单源最短路径：Dijkstra算法
dis[i]是需要不断更新的数组，它表示当前结点1(源点)到其余各结点的最短路径长度~
book[i]标记当前结点最短路径是确定值还是估计值~
算法实现的过程是：每次找到离结点1最近的那个点，然后以该结点为中心扩展，最终得到源点到所有点的最短路径~~每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质~~
找到所有估计值当中最小的值min以及它的结点u，然后把该结点u标记为确定值，通过这个确定值为中转点更新别的所有值的最短路径(松弛别的两个顶点连接的边)

3.Bellman-Ford算法——解决负权边
算法思想：对所有的边进行n-1次“松弛”操作

4.Bellman-Ford的队列优化(SPFA算法)
每次选取首顶点u，对u的所有出边进行松弛操作~如果有一条u->v的边，通过这条边使得源点到顶点v的路程变短，且顶点v不在当前队列中，就把这个顶点v放入队尾。同一个顶点在队列中出现多次是毫无意义的，所以用一个数组来判重复，判断哪些点已经在队列中。对顶点u的所有出边都松弛完毕后，就将顶点v出队~

 

问题描述
　　排序，顾名思义，是将若干个元素按其大小关系排出一个顺序。形式化描述如下：有n个元素a[1]，a[2]，…，a[n]，从小到大排序就是将它们排成一个新顺序a[i[1]]<a[i[2]]<…<a[i[n]]
　　i[k]为这个新顺序。
　　选择排序的思想极其简单，每一步都把一个最小元素放到前面，如果有多个相等的最小元素，选择排位较考前的放到当前头部。还是那个例子：{3 1 5 4 2}：
　　第一步将1放到开头（第一个位置），也就是交换3和1，即swap(a[0],a[1])得到{1 3 5 4 2}
　　第二步将2放到第二个位置，也就是交换3和2，即swap(a[1],a[4])得到{1 2 5 4 3}
　　第三步将3放到第三个位置，也就是交换5和3，即swap(a[2],a[4])得到{1 2 3 4 5}
　　第四步将4放到第四个位置，也就是交换4和4，即swap(a[3],a[3])得到{1 2 3 4 5}
　　第五步将5放到第五个位置，也就是交换5和5，即swap(a[4],a[4])得到{1 2 3 4 5}
　　输入n个整数，输出选择排序的全过程。
　　要求使用递归实现。

　　第一行一个正整数n，表示元素个数
　　第二行为n个整数，以空格隔开
输出格式
　　共n行，每行输出第n步选择时交换哪两个位置的下标，以及交换得到的序列，格式:
　　swap(a[i],a[j]):a[0] … a[n-1]
　　i和j为所交换元素的下标，下标从0开始，最初元素顺序按输入顺序。另外请保证i<=j
　　a[0]…a[n-1]为交换后的序列，元素间以一个空格隔开
样例输入
5
4 3 1 1 2
样例输出
swap(a[0], a[2]):1 3 4 1 2
swap(a[1], a[3]):1 1 4 3 2
swap(a[2], a[4]):1 1 2 3 4
swap(a[3], a[3]):1 1 2 3 4
swap(a[4], a[4]):1 1 2 3 4
数据规模和约定
　　n<=100
　　整数元素在int范围内

 

问题描述
　　某校大门外长度为L的马路上有一排树，每两棵相邻的树之间的间隔都是1米。我们可以把马路看成一个数轴，马路的一端在数轴0的位置，另一端在L的位置；数轴上的每个整数点，即0，1，2，……，L，都种有一棵树。
　　由于马路上有一些区域要用来建地铁。这些区域用它们在数轴上的起始点和终止点表示。已知任一区域的起始点和终止点的坐标都是整数，区域之间可能有重合的部分。现在要把这些区域中的树（包括区域端点处的两棵树）移走。你的任务是计算将这些树都移走后，马路上还有多少棵树。
输入格式
　　输入的第一行有两个整数L（1 <= L <= 10000）和 M（1 <= M <= 100），L代表马路的长度，M代表区域的数目，L和M之间用一个空格隔开。接下来的M行每行包含两个不同的整数，用一个空格隔开，表示一个区域的起始点和终止点的坐标。
输出格式
　　输出包括一行，这一行只包含一个整数，表示马路上剩余的树的数目。
样例输入
500 3
150 300
100 200
470 471
样例输出
298
数据规模和约定
　　对于20%的数据，区域之间没有重合的部分；
　　对于其它的数据，区域之间有重合的情况。
分析：用与l+1等长的数组标记该区域是否有树

 

问题描述
　　元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得的纪念品价值 相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品，并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时 间内发完所有纪念品，乐乐希望分组的数目最少。
　　你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。
输入格式
　　输入包含n+2行：
　　第1行包括一个整数w，为每组纪念品价格之和的上限。
　　第2行为一个整数n，表示购来的纪念品的总件数。
　　第3~n+2行每行包含一个正整数pi (5 <= pi <= w)，表示所对应纪念品的价格。
输出格式
　　输出仅一行，包含一个整数，即最少的分组数目。
样例输入
100
9
90
20
20
30
50
60
70
80
90
样例输出
6
数据规模和约定
　　50%的数据满足：1 <= n <= 15
　　100%的数据满足：1 <= n <= 30000, 80 <= w <= 200
分析：排序+贪心。先从小到大排序，i、j指针分别从左到右、从右到左遍历。
如果a[i]+a[j] <= w，那么把这两个物品都放入同一组，并且同时移动指针；
否则，只能把j所指向的物品放入单独的一个组，移动j指针…直到i j把所有物品都遍历完~

分析下贪心算法的可行性：如果j物品和i物品加起来超过了w，因为j物品比j+1处的物品价值小，那么如果i不能满足加起来的条件，而i-1能满足该条件，是否会影响贪心算法的结果呢？
如果让j和i-1去组合，对于j+1，因为价值比j更大，所以就更放不进i了，所以即使交换组合方式还是不影响构成的组数的~

至于为什么循环的条件是i <= j，当i<j的时候，假设i j已经相邻，那么此时还能再比较一次i+j能否满足构成一组的条件，如果满足就会把它们放到一组，之后i j指针同时移动后i>j不能够满足进入循环的条件了；如果不满足把它们放入一组，那么j放入一组后j移动指针，使i == j，继续进入循环；
当i == j的时候，因为这个单独的物品已经没有可以组合的物品剩余了，所以此时还要进入循环进行一次 cnt++ 的计数操作~//这就是while(i <= j)的解释~~~