M_sea

洛谷3434 [POI2006]KRA-The Disks
题目描述一个框,告诉你每一层的宽度。向下丢给定宽度的木块。木块会停在卡住他的那一层之上,或者是已经存在的木块之上。...
扫描右侧二维码阅读全文
27
2018/07

洛谷3434 [POI2006]KRA-The Disks

题目描述

一个框,告诉你每一层的宽度。

向下丢给定宽度的木块。

木块会停在卡住他的那一层之上,或者是已经存在的木块之上。

询问丢的最后一个木块停在第几层。

传送门

算法

大力模拟。

考虑木块最多上移$n$层。

维护一个$Min[i]$,表示前$i$个数的最小值。
容易发现$Min[i]=min(Min[i-1],a[i])$。

那么对于每一个长度为$k$的木块,当$Min[now]<k$,也就是上面有方块能挡住它时,不断上移。

若上移到0了则直接输出0,然后return 0即可。

注意$a[0]$和$Min[0]$一开始要置成$+\infty$。

代码

#include <bits/stdc++.h>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar();
    return X*w;
}

int a[300010];
int Min[300010];

int main() {
    int n=read(),m=read();
    a[0]=Min[0]=0x7f7f7f7f;
    for (re int i=1;i<=n;i++) a[i]=read(),Min[i]=min(Min[i-1],a[i]);
    
    int now=n+1;
    for (re int i=1;i<=m;i++) {
        int k=read();
        do { now--; } while (Min[now]<k);
        if (!now) { printf("0\n"); return 0; }
    }
    
    printf("%d\n",now);
    return 0;
}
最后修改:2018 年 11 月 09 日 04 : 50 PM

发表评论

2 条评论

  1. smy

    您的$inf$可以设成$1ll<<60$(逃

    1. M_sea
      @smy

      蛤。。。