Home » 國際競賽 » Details

2023-2024年USACO首次月考題目出爐！白金級(jí)第三題真題及解析

Category: 國際競賽, 翰林嚴(yán)選, 計(jì)算機(jī)國際競賽 Date: 2024年1月2日上午11:29

2023-2024賽季的USACO考試已于12月18日正式結(jié)束，晉級(jí)賽的最新試題也已經(jīng)公布。近日，USACO官方公布了2023-2024賽季首場月賽的晉級(jí)分?jǐn)?shù)線。如果沒有晉級(jí)，12月可以當(dāng)做一個(gè)練手+熟悉賽制的環(huán)節(jié)，1、2月的月賽持續(xù)發(fā)力，USACO可以重復(fù)挑戰(zhàn)。

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

USACO 2023年12月白金級(jí)第三題

**Note：The memory limit for this problem is 512MB, twice the default.**

Bessie has taken on a new job as a train dispatcher! There are two train stations：A and B. Due to budget constraints, there is only a single track connecting the stations. If a train departs a station at time t, then it will arrive at the other station at time t+T(1≤T≤10¹²).

There are N (1≤N≤5000) trains whose departure times need to be scheduled. The i th train must leave station s_iat time t_i or later (s_i∈{A,B},0≤t_i≤10¹²). It is not permitted to have trains going in opposite directions along the track at the same time (since they would crash). However, it is permitted to have many trains on the track going in the same direction at the same time (assume trains have negligible size).

Help Bessie schedule the departure times of all trains such that there are no crashes and the total delay is minimized. If train i is scheduled to leave at time a_i≥s_i, the total delay is defined as

INPUT FORMAT (pipe stdin)：

The first line contains N and T.

Then N lines follow, where the ith line contains the station s_i,
and time t_icorresponding to the ith train.

OUTPUT FORMAT (pipe stdout)：

The minimum possible total delay over all valid schedules.

SAMPLE INPUT：

1 95
B 63

SAMPLE OUTPUT：

The only train leaves on time.

SAMPLE INPUT：

4 1
B 3
B 2
A 1
A 3

SAMPLE OUTPUT：

1
There are two optimal schedules. One option is to have trains 2,3,4 leave on time and train 1 leave after a one-minute delay. Another is to have trains 1,2,3 leave on time and train 4 leave after a one-minute delay.

SAMPLE INPUT：

4 10
A 1
B 2
A 3
A 21

SAMPLE OUTPUT：

13
The optimal schedule is to have trains 1and 3 leave on time, train 2 leave at time 13, and train 4 leave at time 23. The total delay is 0+11+0+2=13.

SAMPLE INPUT：

8 125000000000
B 17108575619
B 57117098303
A 42515717584
B 26473500855
A 108514697534
B 110763448122
B 117731666682
A 29117227954

SAMPLE OUTPUT：

548047356974

SCORING：

Inputs 5-6： N≤15
Inputs 7-10： N≤100
Inputs 11-14： N≤500
Inputs 15-18： N≤2000
Inputs 19-24： No additional constraints
Problem credits： Brandon Wang

部分代碼截圖：