題目

?有一口井，井的高度為N，每隔1個(gè)單位它的寬度有變化。現(xiàn)在從井口往下面扔圓盤，如果圓盤的寬度大于井在某個(gè)高度的寬度，則圓盤被卡住（恰好等于的話會(huì)下去）。
盤子有幾種命運(yùn)：1、掉到井底。2、被卡住。3、落到別的盤子上方。
盤子的高度也是單位高度。給定井的寬度和每個(gè)盤子的寬度，求最終落到井內(nèi)的盤子數(shù)量。

如圖井和盤子信息如下：
井：5 6 4 3 6 2 3
盤子：2 3 5 2 4

最終有4個(gè)盤子落在井內(nèi)。

輸入

第1行：2個(gè)數(shù)N, M中間用空格分隔，N為井的深度，M為盤子的數(shù)量(1 <= N, M <= 50000)。
第2 - N + 1行，每行1個(gè)數(shù)，對(duì)應(yīng)井的寬度Wi(1 <= Wi <= 10^9)。
第N + 2 - N + M + 1行，每行1個(gè)數(shù)，對(duì)應(yīng)盤子的寬度Di(1 <= Di <= 10^9)

輸出

輸出最終落到井內(nèi)的盤子數(shù)量。

輸入樣例

7 5
5
6
4
3
6
2
3
2
3
5
2
4

輸出樣例

4

思路：

一開始用單調(diào)棧來維護(hù)，TLE，換了一種方法來做

假設(shè)如果能到達(dá)第 i 層，那么就一定能到達(dá)第 i-1 層，因此如果當(dāng)?shù)?i 層大于第 i-1 層時(shí)，直接令第 i 層等于第 i-1 層即可。

然后對(duì)于 m 個(gè)盤子，初始假設(shè) pos=n，倒著枚舉 n 層，如果第 i 個(gè)盤子小于等于第 pos 層的話，那么說明這個(gè)盤子可以向下落到能落的最底層，這個(gè)時(shí)候能落的盤子數(shù)量+1，pos--，接著枚舉下一個(gè)盤子，直到 pos 為 0

源程序

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 50000+5; const int dx[] = {-1,1,0,0}; const int dy[] = {0,0,-1,1}; using namespace std;int a[N],b[N]; int main() {int n,m;scanf("%d%d",&n,&m);scanf("%d",&a[1]);for(int i=2;i<=n;i++){scanf("%d",&a[i]);if(a[i]>a[i-1])a[i]=a[i-1];}for(int i=1;i<=m;i++)scanf("%d",&b[i]);int res=0;int pos=n;for(int i=1;i<=m;i++){while(pos>0){if(b[i]<=a[pos]){pos--;res++;break;}pos--;}}cout<<res<<endl;return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的扔盘子（51Nod-1279）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。