【正文】 ,1,0 中，所以可以使用時間復(fù)雜度為 ? ?NO 的基數(shù)排序，其它各操作也均能在 ? ?NO 時間內(nèi)完成（具體細(xì)節(jié)留給讀者思考）。 ETTM ??? 21 ， 5000000 ?? S 。 分析： 將每個人的打掃時間看作一個左右端點(diǎn)分別為 iT1 和 iT2 ，且 權(quán)為 iS 區(qū)間。用 ??if 表示在前 i 個區(qū)間中選擇，且第 i 個區(qū)間必須選時，覆蓋 ? ?iTM 2, 的權(quán)和最小值。每得到一個 ??if 的值，就將它插入在 iT2 處，并更新最小值。仔細(xì)分析，可以找到更好的優(yōu)化方法。根據(jù)棧中元素的單調(diào)性，這里可以 用二分查找。 由于棧、二分查找的系數(shù)比線段樹小很多，且棧內(nèi)區(qū)間個數(shù)很少有達(dá)到 N 的情況，故這種優(yōu)化比前面的要好很多。重復(fù)上述操作，直到當(dāng)前區(qū)間能和最小關(guān)鍵字區(qū)間進(jìn)行狀態(tài)轉(zhuǎn)移。 該優(yōu)化時間復(fù)雜度的系數(shù)介于前兩種優(yōu)化之間，然而對于實(shí)現(xiàn) 而言，使用Pascal的編程量和用第一種優(yōu)化差不多，而使用 C/C++就可以大大減少編程量。 該問題雖然可以建立一個二分圖匹配模型，但時間復(fù)雜度顯然太高，應(yīng)該充分利用區(qū)間的性質(zhì)。 命題 P 和 I 至少有一個出現(xiàn)在 S 里。在 S 中可刪除? ?IP?, ，并添加 ? ?IP, 。根據(jù)該算法，顯然有 IP ??? ，所以可將 S 的這兩組匹配改為 ? ?IP,和 ? ?IP ??, 。做預(yù)處理，以區(qū)間左端點(diǎn)為關(guān)鍵字，對它們排序，得到一個有序表。 由于每個區(qū)間只進(jìn)出隊列一次，故一共要進(jìn)行 ??nO 次插入操作和 ??nO 次刪除操作。第 i 個團(tuán)隊有人數(shù) is ，第 j 條旅行線路有人數(shù)下限jl和上限 ju ，只有當(dāng) jij usl ?? 時，第 i 個團(tuán)隊才能選擇第 j 條旅行線路。 23 例題 ： CEOI 2022 Enlightened Landscape 題目大意： 在一片山的上空，高度為 T 處有 ? ?2022 ?? NN 個處于不同水平位置的燈泡（如圖）。 算法： 容易看出，照亮整個山景的充分必要條件是照亮所有的折點(diǎn)。選出最少的點(diǎn)，使每個區(qū)間都至少包含一個所選的點(diǎn)。處理某個區(qū)間時，若該區(qū)間的左端點(diǎn)小于等于 t ，則刪除該區(qū)間，否則更新 t 。如果直接模擬，時間復(fù)雜度為? ?2NMO ，對該題的 數(shù)據(jù)規(guī)模而言，這個算法已經(jīng)可以 AC 了。 while折點(diǎn) i 的高度大于等于折點(diǎn) ? ?kstack 的高度 or 線段（折點(diǎn) ? ?1?kstack ，折點(diǎn) i ）在折點(diǎn) ? ?kstack 上方 {pop} 算出射線（折點(diǎn) i ，折點(diǎn) ? ?kstack ）與直線 Ty? 的交點(diǎn) ? ?Tx,0 利用二分查找找到橫坐標(biāo)大于等于 0x 的最左邊的燈泡 （該燈泡就是能照到 折點(diǎn) i 的最左邊的燈泡） push i 25 【總結(jié)】 區(qū)間問題通常要保持有序性，排序關(guān)鍵字的選擇非常重要。 區(qū)間問題的優(yōu)化大 多可以用到線段樹，極少數(shù)要用到平衡二叉樹，但往往這并不是最佳的優(yōu)化方法。 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。 掛墜的構(gòu)成，是由若干粒綴珠相互連接而成。老板還告訴小 Q，他一共擁有 N 個珠綴（假設(shè)每一個珠綴都很漂亮，小 Q 都很喜歡），每個珠綴都有其各自的重量與承受能力。 接下來 N 行，每行兩個整數(shù) (Ci , Wi)，分別表示第 i 個珠綴的承受能力與重量。 【樣例輸入】 4 3 5 5 1 3 2 4 6 【樣例輸出】 34 3 8 【評分標(biāo)準(zhǔn)】 每一個測試點(diǎn)單獨(dú)評分，對于每一個測試點(diǎn)： 如果掛綴長度 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