集訓隊作業(yè)題目推薦

1、DIVINGpage PAGE 3 of NUMPAGES 3 題目來源：BOI2000推薦人：何林情況：已經(jīng)得到正確算法。希望將算法與提出算法的思路與大家分享。推薦理由：這個題看起來無從下手，而正確的貪心法卻是很簡單的。一個網(wǎng)友給了我一篇論文，我覺得論文中算法的提出和研究的方法都很巧妙，具有很強的可推廣性。希望大家能一起討論研究這種思考方法。DivingEach year there are diving courses in Ohrid. Different tasks are performed during the courses. One of them is to dive fro

2、m one side of the rock through an underwater passage to the other side of the rock. The whole group of N students has only one oxygen bottle. No more then two persons can use the same oxygen bottle at same time. Each diver has its own speed of diving, so when two students dive together they dive wit

3、h speed of the slower one (one with longer diving time). There are M pairs of students that dislike each other and cannot dive together. TaskFind one schedule to move the group of students from one side of the rock to the other side in minimal time.LimitationsN is positive integer and is the number

4、of students in the group.Each student is denoted by 1,2,N.M is positive integer and is the number of student pairs that cannot dive together.ti is positive integer denoting the time required for the i-th student to move from one side of the rock to the other side.The oxygen bottle can only be moved

5、from one side of the rock to the other side by diving. The oxygen bottle has unlimited capacity.There is always at least one solution in the test data.Time limit: 1 sec. Executable file DIVING.EXEInput file DIVING.INThe first line of the input consists of two integers N and M. In each of the next N

6、lines there is one integer ti. In each of the next M lines there are two integers representing a student pair that cannot dive together.Output file DIVING.OUTThe first line of the output contains one integer, the minimal time required for moving all the students. The next lines of the output file ar

7、e reflecting one possible schedule of moves with minimal time. Each line represents one move in the schedule. It consists of one or two integers denoting the student(s) who dive with the oxygen bottle from one side of the rock to the other side. Example DIVING.INDIVING.OUT4 212123 42 363 11 4 233 1潛

8、水每年奧利德湖都有潛水課程。課程中有各項不同的測試。其中一項是通過一條水下通道，從巖石的一端游到另一端。全組N個學生只有一個氧氣瓶，兩個以上的人不能同時使用一個氧氣瓶。每個潛水者有他自己的潛水速度，所以當兩個學生一起潛水時，他們的速度與兩人 中慢的那個（潛水所用時間較長的那個）的速度相同。有M 對學生不喜歡對方，所以不能在一起潛水。 任務(wù)制作一張計劃表，使全組學生從巖石的一端潛到另一端所用的總時間最少。要求N 是個正整數(shù)，表示全組學生的總數(shù)。每個學生按照1,2,N編了號。M是個正整數(shù)，表示不能一起潛水的學生對數(shù)。ti 是個正整數(shù)，表示第i 個學生巖石一端潛到另一端所須的時間。氧氣瓶只能靠潛水的方式從巖石的一端運到另一端。氧氣瓶的容量視為無限。問題至少總有一個解決方案。時間限制: 1 sec. 執(zhí)行文件： DIVING.EXE輸入文件： DIVING.IN第一行是兩個整數(shù)N 和 M，后N 行每行是一個整數(shù)ti 。再后M 行每行是兩個整數(shù)，表示不能在一起潛水的一對學生的編號。輸出文件： DIVING.OUT第一行是個整數(shù)，代表所有學生潛