Home » 國際競賽 » Details

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

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

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

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

銀組第一題

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è)每個塔最下面的數(shù)都是負(fù)無窮，然后從小到大把每一個數(shù)加入塔中。考慮加入塔中的過程，每一次我們都把這個數(shù)加入到之前塔頂數(shù)最小的位置，如果此時不能插入，說明這個數(shù)沒法繼續(xù)插入了。

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

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

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