算法合集之《淺談信息學競賽中的區間問題》-預覽頁

　

【正文】 ,1,0 中，所以可以使用時間復雜度為 ? ?NO 的基數排序，其它各操作也均能在 ? ?NO 時間內完成（具體細節留給讀者思考）。 ETTM ??? 21 ， 5000000 ?? S 。 分析： 將每個人的打掃時間看作一個左右端點分別為 iT1 和 iT2 ，且 權為 iS 區間。用 ??if 表示在前 i 個區間中選擇，且第 i 個區間必須選時，覆蓋 ? ?iTM 2, 的權和最小值。每得到一個 ??if 的值，就將它插入在 iT2 處，并更新最小值。仔細分析，可以找到更好的優化方法。根據棧中元素的單調性，這里可以 用二分查找。 由于棧、二分查找的系數比線段樹小很多，且棧內區間個數很少有達到 N 的情況，故這種優化比前面的要好很多。重復上述操作，直到當前區間能和最小關鍵字區間進行狀態轉移。 該優化時間復雜度的系數介于前兩種優化之間，然而對于實現 而言，使用Pascal的編程量和用第一種優化差不多，而使用 C/C++就可以大大減少編程量。 該問題雖然可以建立一個二分圖匹配模型，但時間復雜度顯然太高，應該充分利用區間的性質。 命題 P 和 I 至少有一個出現在 S 里。在 S 中可刪除? ?IP?, ，并添加 ? ?IP, 。根據該算法，顯然有 IP ??? ，所以可將 S 的這兩組匹配改為 ? ?IP,和 ? ?IP ??, 。做預處理，以區間左端點為關鍵字，對它們排序，得到一個有序表。 由于每個區間只進出隊列一次，故一共要進行 ??nO 次插入操作和 ??nO 次刪除操作。第 i 個團隊有人數 is ，第 j 條旅行線路有人數下限jl和上限 ju ，只有當 jij usl ?? 時，第 i 個團隊才能選擇第 j 條旅行線路。 23 例題 ： CEOI 2022 Enlightened Landscape 題目大意： 在一片山的上空，高度為 T 處有 ? ?2022 ?? NN 個處于不同水平位置的燈泡（如圖）。 算法： 容易看出，照亮整個山景的充分必要條件是照亮所有的折點。選出最少的點，使每個區間都至少包含一個所選的點。處理某個區間時，若該區間的左端點小于等于 t ，則刪除該區間，否則更新 t 。如果直接模擬，時間復雜度為? ?2NMO ，對該題的 數據規模而言，這個算法已經可以 AC 了。 while折點 i 的高度大于等于折點 ? ?kstack 的高度 or 線段（折點 ? ?1?kstack ，折點 i ）在折點 ? ?kstack 上方 {pop} 算出射線（折點 i ，折點 ? ?kstack ）與直線 Ty? 的交點 ? ?Tx,0 利用二分查找找到橫坐標大于等于 0x 的最左邊的燈泡 （該燈泡就是能照到 折點 i 的最左邊的燈泡） push i 25 【總結】 區間問題通常要保持有序性，排序關鍵字的選擇非常重要。 區間問題的優化大 多可以用到線段樹，極少數要用到平衡二叉樹，但往往這并不是最佳的優化方法。 in the second they try to assemble a largest possible gene, by finding a chain with the largest possible number of exons. This chain must obey the order in which the exons appear in the genomic sequence. We say that exon appears before exon j if the end of i precedes the beginning of j. The objective of this problem is, given a set of possible exons, to find the chain with the largest possible number of exons that could be assembled to generate a gene. Input Several input instances are given. Each instance begins with the number 0 n 1000 of possible exons in the sequence. Then, each of the next n lines contains a pair of integer numbers that represent the position in which the exon starts and ends in the genomic sequence. You can suppose that the genomic sequence has at most 50000 basis. The input ends with a line with a single `039。 掛墜的構成，是由若干粒綴珠相互連接而成。老板還告訴小 Q，他一共擁有 N 個珠綴（假設每一個珠綴都很漂亮，小 Q 都很喜歡），每個珠綴都有其各自的重量與承受能力。 接下來 N 行，每行兩個整數 (Ci , Wi)，分別表示第 i 個珠綴的承受能力與重量。 【樣例輸入】 4 3 5 5 1 3 2 4 6 【樣例輸出】 34 3 8 【評分標準】 每一個測試點單獨評分，對于每一個測試點： 如果掛綴長度 L 與答案一 致，且最小重量和 W 也正確，則得 10 分。 （ 例題 ） Europe Southeastern 2022 Problem D Loan Scheduling The North Pole Beach Bank has to decide upon a set App of mortgage applications. Each application a ∈ App has an acceptance deadline da , ie. the required loan must be paid at a time ta , 0≤ ta≤ da . If the application is accepted the Bank gets a profit pa . Time is measured in integral units starting from the conventional time origin 0, when the Bank decides upon all the App applications. Moreover, the Bank can pay a maximum number of L loans at any given time. The Bank policy if focussed solely on profit: it accepts a subset S ∈ App of applications that maximizes the profit ? ? ??? Sa apSprof it. The problem is to pute the maximum profit the Bank can get from the given set App of mortgage applications. For example, consider that L = 1 , App = {a, b, c, d} , (pa, da) = (4, 2) , (pb, db) = (1, 0) , (pc, dc) = (2, 0) , and (pd, dd) = (3, 1) . The table below shows all possible sets of accepted mortgage applications and the 35 scheduling of the loan payments. The highest profit is 9 and corresponds to the set {c, d, a} . The loan requested by the application c is paid at time 0, the loan corresponding to d is paid at time 1, and, finally, the loan of a is paid at time 2. Time Sets of accepted applications and loan scheduling 0 a b c d b c b B c c d d a b c 1 a d d d a a a d d d d 2 a A a a a a a Profit 4 4 4 1 2 3 3 4 5 5 5 6 6 7 7 7 7 8 9 Write a program that reads sets of data from the standard input. Input Each data set corresponds to a set of mortgage applications and starts with two integers: 0≤ N≤ 10000 that shows the number of applications in the set, and 0≤ L≤ 100 which shows the maximum number of loans the Bank can pay at any given time. Follow N pairs of integers pi di , i = 1, N , that specify the profit 0≤ pi≤ 10000 and the deadline 0≤ di≤ 10000 of the application i. Input data are separated by white spaces, are correct, and terminate with an end of file. Output For each data set the program putes the maximum profit the Bank can get from the accepted mortgage applications corresponding to that data set. The result is printed on standard output from the beginning of a line. There must be no empty lines on output. An example of input/output is shown below. Sample Input 4 1 4 2 1 0 2 0 3 1 36 7 2 200 1 200 1 100 0 1000 2 80 1 50 20 500 1 0 100 1 0 4 1000 Sample Output 9 20 50 0 0 (例題 ) ACM/ICPC Regional Warmup Contest 2022 Problem E n sprinklers are installed in a horizontal strip of grass l meters long and w meters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from the left end of the center line and its radius of operation. What is the minimum number of sprinklers to turn on in order to water 37 the entire strip of grass? Input Input consists of a number of cases. The first line for each case contains integer numbers n, l and w with n = 10000. The next n lines contain two integers giving the position of a sprinkler and its radius of operation. (The picture above illustrates the first case from the sample input.) Output For each test case output the minimum number of sprinkler