2023-2024年USACO首次月考題目出爐！銀組第一題真題及解析

Category: 國(guó)際競(jìng)賽, 翰林嚴(yán)選, 計(jì)算機(jī)國(guó)際競(jìng)賽 Date: 2023年12月22日下午4:51

2023-2024賽季UASCO首場(chǎng)月賽已經(jīng)圓滿結(jié)束，晉級(jí)賽的最新試題也已經(jīng)公布。沒能當(dāng)場(chǎng)晉級(jí)的同學(xué)們可以耐心等待一周，一周內(nèi)USACO官方將會(huì)公布本次晉級(jí)賽成績(jī)。如果沒有晉級(jí)，12月可以當(dāng)做一個(gè)練手+熟悉賽制的環(huán)節(jié)，1、2月的月賽持續(xù)發(fā)力，USACO可以重復(fù)挑戰(zhàn)。

今天給大家分享銀級(jí)試題和解析，參賽的同學(xué)來(lái)看看解題思路，沒參賽的同學(xué)來(lái)看看難度如何？

銀組第一題

INPUT FORMAT（pipe stdin）：The first line contains three space-separated integers,N,M,K.The next N lines contain two space-separated integers, wi and ai.

It is guaranteed that all wi are distinct.

OUTPUT FORMAT (pipe stdout)：

Output the maximum number of cows in balanced towers if FJ helps the cows form towers optimally.

SAMPLE INPUT：

3 5 2

9 4

7 6

5 5

SAMPLE OUTPUT：

FJ can create four balanced towers with cows of weights 5,7 and 9, and one balanced tower with cows of weights 5 and 7.

SAMPLE INPUT：

3 5 3

5 5

7 6

9 4

SAMPLE OUTPUT：

FJ can create four balanced towers with cows of weights 5 and 9,

and one balanced tower with a cow of weight 7. Alternatively, he can create four balanced towers with cows of weights 5 and 9, and one balanced tower with a cow of weight 5.

SCORING：

In inputs 3-5, M <= 5000 and the total number of cows does not exceed 5000.

In inputs 6-11, the total number of cows does not exceed 2*10**5

Inputs 12-17 have no additional constraints.

試題解析考慮從前往后貪心，首先假設(shè)每個(gè)塔最下面的數(shù)都是負(fù)無(wú)窮，然后從小到大把每一個(gè)數(shù)加入塔中。考慮加入塔中的過程，每一次我們都把這個(gè)數(shù)加入到之前塔頂數(shù)最小的位置，如果此時(shí)不能插入，說明這個(gè)數(shù)沒法繼續(xù)插入了。

由于每種數(shù)有很多個(gè)，一個(gè)個(gè)插入時(shí)間復(fù)雜度會(huì)過大，考慮將每種數(shù)作為一個(gè)整體插入。在當(dāng)前這種數(shù)插入在另一種數(shù)的上方的時(shí)候，要么另一種數(shù)完全覆蓋，要么當(dāng)前這種數(shù)被用完，所以每種數(shù)最多被考慮一次。

時(shí)間復(fù)雜度：O(nlogn）知識(shí)點(diǎn)：貪心，排序

USACO歷年真題及參考書，掃碼領(lǐng)取！【翰林提供報(bào)名指導(dǎo)服務(wù)】USACO歷年真題及參考書