题解：CF272C Dima and Staircase

xktc12 · 2024-08-29 19:30:07 · 题解

题意

Dima 有一个楼梯，由 n 阶台阶组成。台阶从左到右的高度依次为 a_1,a_2,\cdots,a_n（保证不下降）。Dima 将宽度为 w ，高度为 h 的箱子对齐楼梯左上角垂直放下，箱子会掉到楼梯上。箱子掉落在楼梯上的位置规定如下：箱子底部碰到楼梯或是其他箱子顶部就会水平停放在该位置。要求 Dima 连续将 m 个箱子抛出后，求每个箱子的停放高度。

也就是说有 n 个台阶和 m 个箱子，并且箱子底部碰到楼梯或是其他箱子顶部就会水平停放在该位置。

思路

当前宽度为 w 的箱子，要么碰到第 w 级台阶停下，要么碰到之前停下的箱子然后停下。因为保证楼梯不下降（刚好可以降低时间复杂度），所以每次记录最高点即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    long long n,m,Max=-10000;
    cin>>n;
    long long a[n+5]={};
    for(int i=1;i<=n;i++)cin>>a[i];
    cin>>m;
    while(m--){
        long long w,h;
          cin>>w>>h;
          Max=max(Max,a[w]);
          cout<<Max<<"\n";
          Max+=h;
    }
    return 0;
}