Rolete

2026年8月25日 · 阅读需 6 分钟

[COCI 2023/2024 #5] Rolete

题干

题目背景

译自 COCI 2023/2024 Contest #5 T4「Rolete」

题目描述

一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。

卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘：

他可以手动开始拉起任意一个窗帘。使用这种方法，他每拉起 $1$ 厘米需要 $t$ 秒钟。
他可以按下一个按钮，同时以相同的速度将所有窗帘同步拉起。

按下按钮时，窗帘的上升速度定义如下：如果所有窗帘都在上升，每个窗帘都会在 $s$ 秒内上升 $1$ 厘米。如果 $r$ 个窗帘已经完全升起，这会减慢系统的速度。那么剩余的窗帘每上升 $1$ 厘米需要 $s + k \cdot r$ 秒钟。

COCI 即将开始，Luka 希望尽快拉起他的窗帘。与此同时，他的兄弟 Marin 走进房间，问了他 $q$ 个问题：为了使窗帘下降的最大高度不超过 $h$ 厘米，你需要的最短时间是多少？Marin 对于每个问题都考虑窗帘的初始状态。

他们意识到在 COCI 之前没有足够的时间来考虑这个问题。幸运的是，这个问题也出现在这里！帮助他们解决它！

注意：Luka 总是将窗帘拉起一个整数值的厘米。

输入格式

第一行四个整数 $n,t,s,k\ (1\le n,t,s\le 10^5,0\le k\le 10^5)$ ，分别表示窗帘个数，手动拉窗帘所需的时间，按下按钮拉窗帘所需的时间和同步上升的减慢因子。

第二行包含 $n$ 个整数 $a_i\ (0\le a_i\le 10^5)$ ，表示初始窗帘的状态。

第三行包含一个整数 $q\ (1\le q\le 10^5)$ ，表示问题个数。

第四行包含 $q$ 个整数 $h_i\ (0\le h_i\le 10^5)$ ，表示最大窗帘高度。

输出格式

输出一行 $q$ 个整数，第 $i$ 个表示使得窗帘下降的最大高度不超过 $h_i$ 厘米所需的最短用时。

输入输出样例 #1

输入 #1

输出 #1

4 14 9

输入输出样例 #2

输入 #2

输出 #2

0 3 10

输入输出样例 #3

输入 #3

输出 #3

9 18 47

说明/提示

样例解释 1

为了使所有窗帘的下降高度最多为 $2$ 厘米，卢卡需要手动将第三个窗帘拉起 $2$ 厘米。最快的方法是手动拉起它，这将花费他 $4$ 秒钟。

如果所有窗帘都需要完全拉起，卢卡可以先手动将第三个窗帘拉起 $2$ 厘米。然后，他可以按下按钮，让所有窗帘同时上升 $2$ 厘米。总共需要的时间为 $4 + 10 = 14$ 秒。

类似地，如果窗帘的下降高度最多为 $1$ 厘米，卢卡会先手动将第三个窗帘拉起 $2$ 厘米，然后将所有窗帘一起上升 $1$ 厘米。拉起的总时间将为 $9$ 秒。

子任务

Subtask	Points	Constraints
1	16	$n,q,a_i,h_i\le 100$
2	26	$k=0$
3	32	$q=1$
4	36	无额外限制

分析

考虑贪心
首先，当高度极高的时候它的代价一定是 $0$ (不用拉就都满足)，我们考虑从高到低计算
当我们从计算高度 $h$ 的答案时，我们直接考虑从 $h+1$ 的最优答案去转移
因为要少花费用，所以我们每次在上一个基础上将所以更高的 $-1$ 就可以了
此时我们发现要么将更高的全部单个降低，要么用一次全局降低，选择费用较低的并记录即可
以下是一段比较感性的证明
如果你 $x+1$ 的情况用这种方法得到了最优解，并且 $x$ 的时候用这种方法得不到最优解
那么你一定是因为调整上面的某一步操作会让之前的代价更大但是此时的代价最小
显然如果会这样要么是之前用 $1$ 代价更大但是如果用 1 可以减小本次使用 2 操作的代价
但是如果你之前用 2 现在用 1 的操作代价是一样的，所以你之前用 $2$ 是不劣的
或者是之前用 $2$ 代价更大但是用 $2$ 操作可以拉下去一些本来不需要拉的窗帘，让你 $1$ 操作的代价更小
但是你之前用 $1$ 这下用 $2$ 肯定也是不劣的
而对于这道题，我们还存在一个二分套三分的代码，它的思路也可以数学严谨的证明这个贪心的正确性
时间复杂度 $O(q)$

AC代码

Code

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair< int,int >
#define QWQ return 0;
#define QAQ return 
#define intt __int128_t

const int N=1e5+10, m=1e5;

int pre[N], bck[N], all[N]; 
intt ans[N];

inline void print( intt x )
{
	if( x > 9 ) print( x/10 );
	putchar( x%10+'0' );
}

int main()
{
    // freopen( "1.in","r",stdin );
    // freopen( "1.out","w",stdout );
    ios::sync_with_stdio( false );
    cin.tie( nullptr ); cout.tie( nullptr );
    int n, t, s, k;
    cin>>n>>t>>s>>k;
    for( int i=1, h;i<=n;i++ )
        cin>>h,
        pre[h]++, bck[h]++;
    for( int i=1;i<=m;i++ )   pre[i]+=pre[i-1];
    for( int i=m-1;i>=0;i-- ) bck[i]+=bck[i+1];
    for( int i=m-1;i>=0;i-- )
    {
        intt fee1=( intt )bck[i+1+all[i+1]]*t;
        intt fee2=( intt )s+( intt )k*pre[all[i+1]];
        if( fee1 <= fee2 ) ans[i]=ans[i+1]+fee1, all[i]=all[i+1];
        else               ans[i]=ans[i+1]+fee2, all[i]=all[i+1]+1;
    }
    int q, x;
    for( cin>>q;q;q-- ) cin>>x, print( ans[x] ), putchar( ' ' );
    QWQ
}

[COCI 2023/2024 #5] Rolete​