算法与程序设计竞赛 第五章 STL.ppt

Program Design Example: Rating the Field Pretty Polly has no shortage of gentlemen suitors who come a’ courting. Indeed, her biggest problem is keeping track of who the best ones are. She is smart enough to realize that a program which ranks the men from most to least desirable would simplify her life. She is also persuasive enough to have talked you into writing the program. Polly really likes to dance, and has determined the optimal partner height is 180 centimeters tall. Her first criteria is finding someone who is as close as possible to this height; whether they are a little taller or shorter doesn’t matter. Among all candidates of the same height, she wants someone as close as possible to 75 kilograms without going over. If all equal-height candidates are over this limit, she will take the lightest of the bunch. If two or more people are identical by all these characteristics, sort them by last name, then by first name if it is necessary to break the tie. Polly is only interested in seeing the candidates ranked by name, so the input file: George Bush 195 110 Harry Truman 180 75 Bill Clinton 180 75 John Kennedy 180 65 Ronald Reagan 165 110 Richard Nixon 170 70 Jimmy Carter 180 77 yields the following output: Clinton, Bill Truman, Harry Kennedy, John Carter, Jimmy Nixon, Richard Bush, George Reagan, Ronald Solution The key to this problem is sorting under a fairly complex criteria defined over multiple fields. There are at least two different ways we can do this. The first makes multiple sorting passes, sorting first on the least important key, then the next least important key, and so on until we finally sort on the major key. Why do we sort in this order? The minor keys are only used to break ties among the major key ordering. Provided our sorting algorithm is stable, meaning it preserves the relative order of equal keys, our work on the minor keys remains intact if it is relevant to the final answer. Not all sorting algorithms are stable: indeed most fas